Description
Return the length of a longest sequence of characters appearing in order in both strings, without requiring adjacency.
Solution
def longest_common_subsequence(text1, text2):
row = [0]*(len(text2)+1)
for a in text1:
diagonal = 0
for j,b in enumerate(text2,1):
old = row[j]
row[j] = diagonal+1 if a == b else max(row[j],row[j-1])
diagonal = old
return row[-1]Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
["abc","ac"]- Output
2
a and c occur in order in both strings.
Example 2
- Input
["abc","xyz"]- Output
0
No characters are shared.
Example 3
- Input
["aaa","aa"]- Output
2
Two a characters can be matched.
Approach
Match equal characters using the diagonal predecessor; otherwise keep the better result from dropping either character.
Time & space
O(n m) time; O(m) space for the two string lengths.