dfs
go
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 j := range dp[i] {
dp[i][j] = -1
}
}
return dfs(text1, text2, len(text1), len(text2), dp)
}
func dfs(s, t string, i, j int, dp [][]int) int {
if dp[i][j] > -1 {
return dp[i][j]
}
if i == 0 || j == 0 {
dp[i][j] = 0
return 0
}
if s[i-1] == t[j-1] {
dp[i][j] = 1 + dfs(s, t, i-1, j-1, dp)
return dp[i][j]
}
dp[i][j] = max(dfs(s, t, i-1, j, dp), dfs(s, t, i, j-1, dp))
return dp[i][j]
}dp
go
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 := range text1 {
for j := range text2 {
if text1[i] == text2[j] {
dp[i+1][j+1] = 1 + dp[i][j]
} else {
dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
}
}
}
return dp[m][n]
}dp space compress
go
func longestCommonSubsequence(text1 string, text2 string) int {
m, n := len(text1), len(text2)
dp := [2][]int{}
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := range text1 {
for j := range text2 {
if text1[i] == text2[j] {
dp[(i+1)&1][j+1] = 1 + dp[i&1][j]
} else {
dp[(i+1)&1][j+1] = max(dp[(i+1)&1][j], dp[i&1][j+1])
}
}
}
return dp[m&1][n]
}