The title

  1. 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.