vladimir.ovsyannikov
BAN USERsimple python solution
def get_length(positions):
keys = positions.keys()
max_ = min_ = positions[keys[0]]
for k in keys:
max_ = max(max_, positions[k])
min_ = min(min_, positions[k])
if min_ == -1:
return -1, min_
return (max_ - min_, min_)
def mix_sub(string, template):
freq = {}
for t in template:
freq[t] = -1
start = -1
l = len(string)
for i in xrange(len(string)):
s = string[i]
if s in freq:
freq[s] = i
(length, min) = get_length(freq)
if 0 < length < l:
l = length
start = min
return string[start: start +l + 1]
python version
def merge(left, right):
p_left = 0
p_right = 0
result = []
if left[p_left][0] <= right[p_right][0]:
start = left[p_left][0]
end = left[p_left][1]
p_left +=1
else:
start = right[p_right][0]
end = right[p_right][1]
p_right += 1
while p_left < len(left) or p_right < len(right):
if p_left < len(left) and start <= left[p_left][0] and end >= left[p_left][0]:
end = max(end, left[p_left][1])
p_left += 1
elif p_right < len(right) and start <= right[p_right][0] and end >= right[p_right][0]:
end = max(end, right[p_right][1])
p_right += 1
else:
result.append((start, end))
if p_left < len(left) and p_right < len(right):
start = min(left[p_left][0], right[p_right][0])
end = left[p_left][1] if start == left[p_left][0] else right[p_right][1]
elif p_left < len(left):
start = left[p_left][0]
end = left[p_left][1]
else:
start = right[p_right][0]
end = right[p_right][1]
result.append((start, end))
return result
simple python solution
- vladimir.ovsyannikov March 27, 2016