LeetCode: Longest Common Subsequence

Posted on September 1, 2019July 26, 2020 by braindenny

Longest Common Subsequence

Similar Problems:

Given two strings text1 and text2, return the length of their longest common subsequence.

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. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

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 <= 1000
1 <= text2.length <= 1000
The input strings consist of lowercase English characters only.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/longest-common-subsequence
// Basic Ideas: 2D dynamic programming
//  Optimal substructure:
//      s1[0...i]
//      s2[0...j]
//      if s1[i] == s2[j], only need to know the case of s1[0...i-1], s2[0...j-1]
//      Otherwise, evaluate two cases: s1[0...i], s2[0...j-1]; s1[0...i-1], s2[0...j]
//  Termination condition:
//      s1[0...0], s2[0...0]
// Complexity: Time O(n*m), Space O(min(n, m))
func longestCommonSubsequence(text1 string, text2 string) int {
    if len(text2) > len(text1) {
        text1, text2 = text2, text1
    }
    dp := make([]int, len(text2)+1)
    for i:=0; i<len(text1); i++ {
        l := make([]int, len(dp))
        copy(l, dp)
        for j:=1; j<len(dp); j++ {
            // text1[0:i+1] text2[0:j+1]
            if text1[i] == text2[j-1] {
                if i != 0 {
                    dp[j] = l[j-1]+1
                } else {
                    dp[j] = 1
                }
            } else {
                dp[j] = l[j]
                if dp[j] < dp[j-1] {
                    dp[j] = dp[j-1]
                }
            }
        }
    }
    return dp[len(dp)-1]
}

// https://code.dennyzhang.com/longest-common-subsequence
// Basic Ideas: 2D dynamic programming
//  dp(i, j) <- s1[0:i+1] s2[0:j+1]
//      if s1[i] == s2[j], dp(i-1, j-1)+1
//      if s1[i] != s2[j], max(dp(i, j-1), dp(i-1, j-1))
//  Notice: Use padding to avoid lengthy initialization
// Complexity: Time O(n*m), Space O(n*m)
func longestCommonSubsequence(text1 string, text2 string) int {
    dp := make([][]int, len(text1)+1)
    for i, _ := range dp {
        dp[i] = make([]int, len(text2)+1)
    }
    for i:=1; i<len(dp); i++ {
        for j:=1; j<len(dp[0]); j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1]+1
            } else {
                dp[i][j] = dp[i-1][j]
                if dp[i][j]<dp[i][j-1] {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }
    return dp[len(dp)-1][len(dp[0])-1]
}

Post Views: 0