Longest Common Subsequence
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
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 <= 1000
text1 and text2 consist of only lowercase English characters.
imagine looong strings
abncsdgs…..fsfsd vs asfdagfd….fasdfas
lets look at the last letters
if I knew the common length up until there, i could just add 1 if the last letters are the same or add 0 if different
func longestCommonSubsequence(word1, word2 string) int {
return lcsHelper(word1, word2, len(word1), len(word2))
}
func lcsHelper(word1, word2 string, m, n int) int {
// Base case: If either of the words is empty, LCS is 0.
if m == 0 || n == 0 {
return 0
}
// If the characters match, include them in the LCS.
if word1[m-1] == word2[n-1] {
return 1 + lcsHelper(word1, word2, m-1, n-1)
}
// If characters don't match, take the maximum LCS from the previous states.
return max(lcsHelper(word1, word2, m-1, n), lcsHelper(word1, word2, m, n-1))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
here we can save some calls by remembering the result of a previous call
for example look at the lcsHelper(word1, word2, m-1, n-1) call
maybe it’s called with the same args multiple times
what if we save the result of this call to an array and look up if we need it again
func longestCommonSubsequence(text1 string, text2 string) int {
m, n := len(text1), len(text2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if text1[i-1] == text2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
}
}
}
return dp[m][n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
here dp[i-1][j-1] keeps the result of lcsHelper(word1, word2, m-1, n-1) call
we can also follow dp a table
iterate the first row
s vs e
0 common
| s e a
---|------------
| 0 0 0 0
e | 0 **0** 0 0
a | 0 0 0 0
t | 0 0 0 0
se vs e 1
| s e a
---|------------
| 0 0 0 0
e | 0 0 1 0
a | 0 0 0 0
t | 0 0 0 0
sea vs e 1
| s e a
---|------------
| 0 0 0 0
e | 0 0 1 1
a | 0 0 0 0
t | 0 0 0 0
2nd row
s vs ea 0
| s e a
---|------------
| 0 0 0 0
e | 0 0 1 0
a | 0 0 0 0
t | 0 0 0 0
se vs ea 1
| s e a
---|------------
| 0 0 0 0
e | 0 0 1 0
a | 0 0 1 0
t | 0 0 0 0
sea vs ea 2 common
| s e a
---|------------
| 0 0 0 0
e | 0 0 1 0
a | 0 0 1 2
t | 0 0 0 0
3rd row
s vs eat 0
| s e a
---|------------
| 0 0 0 0
e | 0 0 1 0
a | 0 0 1 2
t | 0 0 0 0
se vs eat
| s e a
---|------------
| 0 0 0 0
e | 0 0 1 0
a | 0 0 1 2
t | 0 0 1 0
sea vs eat
| s e a
---|------------
| 0 0 0 0
e | 0 0 1 0
a | 0 0 1 2
t | 0 0 1 2
at each step, it’s enough to know the results of 3 prev calls
dp[i-1][j-1], dp[i][j-1], dp[i-1][j]
It means we don’t have remember all the table
func longestCommonSubsequence(word1, word2 string) int {
m, n := len(word1), len(word2)
// Ensure m is the smaller of the two lengths for space optimization.
if m > n {
word1, word2 = word2, word1
m, n = n, m
}
// Use a 1D DP slice to store the current row.
dp := make([]int, n+1)
for i := 1; i <= m; i++ {
prev := 0 // Store the value from the previous row and column.
for j := 1; j <= n; j++ {
temp := dp[j] // Store the current value in dp[j].
if word1[i-1] == word2[j-1] {
dp[j] = prev + 1
} else {
dp[j] = max(dp[j], dp[j-1])
}
prev = temp // Update prev with the stored value.
}
}
return dp[n]
}