Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for DNA Common Sequence by Moff
class LCS(object):
def __init__(self, x, y):
self.x = x
self.y = y
self.length = self.calc_length(x, y)
@staticmethod
def calc_length(x, y):
m = len(x)
n = len(y)
c = [[0] * (n + 1) for _ in range(m + 1)]
for i, cx in enumerate(x):
for j, cy in enumerate(y):
if cx == cy:
c[i+1][j+1] = c[i][j] + 1
else:
c[i+1][j+1] = max(c[i+1][j], c[i][j+1])
return c
def calc_all(self):
return self.backtrack_all(self.length, self.x, self.y, len(self.x), len(self.y))
@classmethod
def backtrack_all(cls, c, x, y, i, j):
if i == 0 or j == 0:
return {''}
elif x[i-1] == y[j-1]:
return set(z + x[i-1] for z in cls.backtrack_all(c, x, y, i-1, j-1))
else:
res = set()
if c[i][j-1] >= c[i-1][j]:
res = cls.backtrack_all(c, x, y, i, j-1)
if c[i-1][j] >= c[i][j-1]:
res = res.union(cls.backtrack_all(c, x, y, i-1, j))
return res
def common(s1, s2):
return ','.join(sorted(LCS(s1, s2).calc_all()))
Aug. 22, 2015
