Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for DNA Common Sequence by bukebuer
def common(first, second):
m, n = len(first), len(second)
first, second = '.' + first, '.' + second
# get LCS map
c = [[0] * (n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if first[i] == second[j]:
c[i][j] = c[i-1][j-1] + 1
elif c[i-1][j] == c[i][j-1]:
c[i][j] = c[i-1][j]
elif c[i-1][j] > c[i][j-1]:
c[i][j] = c[i-1][j]
else:
c[i][j] = c[i][j-1]
if c[m][n] == 0: return ''
# find all LCS recursively
routes, to_search = set([]), {(m, n): set([''])}
while to_search:
temp = {}
for i,j in to_search:
if i*j == 0:
routes |= set(to_search[(i,j)])
elif first[i] == second[j]:
temp[(i-1, j-1)] = temp.get((i-1, j-1), set([])) | \
set([first[i]+r for r in to_search[(i,j)]])
elif c[i-1][j] == c[i][j-1]:
temp[(i-1, j)] = temp.get((i-1, j), set([])) | to_search[(i,j)]
temp[(i, j-1)] = temp.get((i, j-1), set([])) | to_search[(i,j)]
elif c[i-1][j] > c[i][j-1]:
temp[(i-1, j)] = temp.get((i-1, j), set([])) | to_search[(i,j)]
else:
temp[(i, j-1)] = temp.get((i, j-1), set([])) | to_search[(i,j)]
to_search = temp
return ','.join(sorted(list(routes)))
Dec. 29, 2014
Comments:
