1143. Longest Common Subsequence

LeetCode 1143. Longest Common Subsequence

Description

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

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.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

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.

Constraints:

• 1 <= text1.length, text2.length <= 1000

• text1 and text2 consist of only lowercase English characters.

Tags

Dynamic Programming

Solution

双串LCS问题。dp[i][j]表示第一串[0..i]，第二串[0..j]的LCS，故有两种可能，i和j指向的字符一致，则dp[i][j]=1+dp[i-1][j-1] ，否则有两种前一个状态转移到当前状态，取最大者，即dp[i][j]=max(dp[i-1][j], dp[i][j-1]) 。遍历二维数组时两指针均是[1, len(text)]闭区间，指针表示字符之间的空隙，dp[0][j]=dp[i][0]=0，表示空字符串没有LCS。最后返回右下角。

Complexity

• Time complexity: $O(n^2)$

• Space complexity: $O(n^2)$

Code

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(text1); i++ {
		for j := 1; j <= len(text2); j++ {
			if text1[i-1] == text2[j-1] {
				dp[i][j] = 1 + dp[i-1][j-1]
			} else {
				dp[i][j] = max(dp[i][j-1], dp[i-1][j])
			}
		}
	}
	return dp[len(text1)][len(text2)]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}