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:

// Blog link: 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] }

// Blog link: 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] }