Short Problem Definition:
Given two strings a and b of equal length, what’s the longest string (S) that can be constructed such that it is a child of both?
A string x is said to be a child of a string y if x can be formed by deleting 0 or more characters from y.
Link
Complexity:
time complexity is O(N*M)
space complexity is O(N*M)
Execution:
This is a longest common subsequence problem in disguise. I encourage you to look at a good explanation here.
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#!/usr/bin/py def lcs(a, b): lengths = [[ 0 for j in range ( len (b) + 1 )] for i in range ( len (a) + 1 )] for i, x in enumerate (a): for j, y in enumerate (b): if x = = y: lengths[i + 1 ][j + 1 ] = lengths[i][j] + 1 else : lengths[i + 1 ][j + 1 ] =
max (lengths[i + 1 ][j], lengths[i][j + 1 ]) return lengths[ - 1 ][ - 1 ] def main(): s1 = raw_input () s2 = raw_input () print lcs(s1,s2) if __name__ = = '__main__' : main() |