The title
- Longest common subsequence
Topic describes
Given two strings text1 and text2, return the length of the longest common subsequence of the two strings.
A subsequence of a string is a new string made up of the original string without changing the relative order of the characters by deleting some characters (or none). For example, “ace” is a subsequence of “ABCDE”, but “AEC” is not a subsequence of “ABCDE”. A “common subsequence” of two strings is a subsequence that is shared by both strings.
Returns 0 if the two strings have no common subsequence.
case
# # # # example 1:
Enter: text1 ="abcde", text2 = "ace"Output:3Explanation: The longest common subsequence is"ace"And its length is zero3.Copy the code
Example 2:
Enter: text1 ="abc", text2 = "abc"Output:3Explanation: The longest common subsequence is"abc"And its length is zero3.Copy the code
Example 3:
Enter: text1 ="abc", text2 = "def"Output:0Explanation: Two strings have no common subsequence, return0.Copy the code
Train of thought
Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp tabel Dp [I][j] Columns and rows indexed to 0 represent empty strings, that is, dp[…] [0] and dp [0] […]. Both represent 0 state transition equation:
if text1[i] == text2[j] {
dp[i][j] = dp[i- 1, j- 1] + 1
}
iftext1[i] ! = text2[j] { dp[i][j] = max(dp[i- 1, j], dp[i, j- 1])}Copy the code
code
package leetcode
import(
"log"
)
// longestCommonSubsequence
// 1143. Longest common subsequence
func longestCommonSubsequence(text1 string, text2 string) int {
w := len(text1)
h := len(text2)
// base case
/ / initialization
dp := MakeIntSlice(w+1, h+1)
log.Println(dp)
for i:=1; i<=w; i++ {
for j:=1; j<=h; j++ {
// State transition
if text1[i- 1] == text2[j- 1] {
dp[i][j] = dp[i- 1][j- 1] +1
} else {
dp[i][j] = max(dp[i- 1][j], dp[i][j- 1])}}}return dp[w][h]
}
func max(a, b int) int{
if a > b {
return a
}
return b
}
// MakeSlice
// Create a 2d slice
func MakeIntSlice(row, column int)[] []int {
data := make([] []int, row)
for index := range data {
data[index] = make([]int, column)
}
return data
}
Copy the code
reference
Source: LeetCode link: leetcode-cn.com/problems/lo… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.