LC 1143 - Longest Common Subsequence
Question
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
- For example,
"ace"is a subsequence of"abcde".
A common subsequence of two strings is a subsequence that is common to both strings.
Example 1:
1
2
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.
Example 2:
1
2
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is “abc” and its length is 3.
Example 3:
1
2
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
Constraints:
1 <= text1.length, text2.length <= 1000text1andtext2consist of only lowercase English characters.
Links
Question here and solution here
Solution
concept
From the brute force solution, we can see that whenever we have a match char, i.e. text1[i] == text2[j], we can search the next index of both of the strings (and plus 1 to the next search since we found one char in the LCS). If we do not see a match, we can then DFS the next index of either the string and get the maximum of the two.
The bottom-up solution is pretty much the same. Imagine we put the two string in the 2D board, with an extra col and row equal to 0 for ease of calculations. Whenever we see that the char matches, we take the diagonal (bottom-right) value and +1. Whenever the char does not match, this cell is the max(right cell, bottom cell)
Each cell is the LCS of the text1[i:] and text[j:] 
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution:
"""
brute force backtracking
TLE
"""
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
def dfs(i,j):
if i == len(text1) or j == len(text2):
return 0
if text1[i] == text2[j]:
ans = 1 + dfs(i+1, j+1)
else:
ans = max(dfs(i+1,j), dfs(i, j+1))
return ans
return dfs(0,0)
class Solution:
"""
top down solution: memoization
"""
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
# (i,j) -> longest common subsequence at that i,j
cache = {}
def dfs(i,j):
if i == len(text1) or j == len(text2):
return 0
if (i,j) in cache:
return cache[(i,j)]
if text1[i] == text2[j]:
ans = 1 + dfs(i+1, j+1)
else:
ans = max(dfs(i+1,j), dfs(i, j+1))
cache[(i,j)] = ans
return cache[(i,j)]
return dfs(0,0)
class Solution:
"""
bottom up solution
"""
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]
for i in range(len(text1)-1, -1, -1):
for j in range(len(text2)-1, -1, -1):
if text1[i] == text2[j]:
dp[i][j] = 1 + dp[i+1][j+1]
else:
dp[i][j] = max(dp[i+1][j], dp[i][j+1])
return dp[0][0]
Complexity
time: $O(mn)$
space: $O(mn)$