Christiana S. F. Chamon - 3 months ago 16
Python Question

# Longest Common Subsequence Python 2 function

When I run LCS( 'human', 'chimp' ), I'm getting "h" instead of "hm".
When I run LCS( 'gattaca', 'tacgaacta' ), I'm getting "g" instead of "gaaca".
When I run LCS( 'wow', 'whew' ), I'm getting "ww" which is correct.
When I run LCS( '', 'whew' ), I'm getting "" which is correct.
When I run LCS( 'abcdefgh', 'efghabcd' ), I'm getting "a" instead of "abcd".
What am I doing incorrectly?

Here is my code:

``````def LCS(S, T):
array = ''
i = 0
j = 0
while i < len(S):
while j < len(T):
if S[i] == T[j]:
array += S[i]
j += 1
i += 1
return array
``````

Figured it out thanks to the people next to me in the lab! It would also be nice to not run into snooty people on Stack Overflow every now and then.

``````def LCS(S, T):
# If either string is empty, stop
if len(S) == 0 or len(T) == 0:
return ""

# First property
if S[-1] == T[-1]:
return LCS(S[:-1], T[:-1]) + S[-1]

# Second proprerty
# Last of S not needed:
result1 = LCS(S[:-1], T)
# Last of T not needed
result2 = LCS(S, T[:-1])
if len(result1) > len(result2):
return result1
else:
return result2
``````
Source (Stackoverflow)