How do you find the length of the longest common subsequence of two strings?
You build a table where each entry is the length of the longest common subsequence of the two parts of the strings that lead up to that point.
def lcs_length(a, b):
rows, cols = len(a), len(b)
table = [[0] * (cols + 1) for _ in range(rows + 1)]
for i in range(1, rows + 1):
for j in range(1, cols + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1] + 1
else:
table[i][j] = max(table[i - 1][j], table[i][j - 1])
return table[rows][cols]
So how does it work? The row i stands for the first i characters of the first string, and the column j stands for the first j characters of the second string. And the entry at that place is the length of the longest common subsequence of those two parts.
And there are two cases at each cell. If the two characters are the same then you can add that character to the longest common subsequence of the parts before them, so the answer is one more than the entry above and to the left. If they are different then you have to leave one of them out, so the answer is the bigger of the entry above and the entry to the left.
the strings "abcde" and "ace"
the table
"" a c e
"" 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3
the answer is 3, and the subsequence is a, c, e
And there is a detail worth knowing about. A subsequence keeps the order of the characters but it does not have to be next to each other. So the answer for "abcde" and "ace" is three and not one, because you can skip the b and the d.
And the complexity is O of the length of a times the length of b for the time, and the same for the space.
So the rule to remember is this. When the characters match, take the one above and to the left and add one.
The last question in this topic shows how to rebuild the subsequence itself.