Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DNA Common Sequence solution in Uncategorized category for DNA Common Sequence by capback250
def common(a, b):
table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a)+1):
for j in range(1, len(b)+1):
if a[i-1] == b[j-1]:
table[i][j] = table[i-1][j-1] + 1
else:
table[i][j] = max(table[i][j-1], table[i-1][j])
return ','.join(sorted(backTrackAll(table, a, b, len(a), len(b))))
def backTrackAll(C, X, Y, i, j):
if i == 0 or j == 0:
return set([""])
elif X[i-1] == Y[j-1]:
return set([Z + X[i-1] for Z in backTrackAll(C, X, Y, i-1, j-1)])
else:
r = set()
if C[i][j-1] >= C[i-1][j]:
r.update(backTrackAll(C, X, Y, i, j-1))
if C[i-1][j] >= C[i][j-1]:
r.update(backTrackAll(C, X, Y, i-1, j))
return r
Feb. 8, 2016