1143. Longest Common Subsequence

Problem

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.

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, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

Problem Summary

Given two strings text1 and text2, return the length of the longest common subsequence of these two strings. If there is no common subsequence, return 0. A subsequence of a string is a new string formed from the original string by deleting some characters (or none) without changing the relative order of the remaining characters. 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 both strings have in common.

Solution Approach

This is the classic longest common subsequence problem. The solution approach is two-dimensional dynamic programming. Suppose the lengths of strings text1 and text2 are m and n respectively. Create a two-dimensional array dp with m+1 rows and n+1 columns, and define dp[i][j] as the length of the longest common subsequence of text1[0:i-1] with length i and text2[0:j-1] with length j. First consider the boundary conditions. When i = 0, text1[] is an empty string, and the length of its longest common subsequence with any string is 0, so dp[0][j] = 0. Similarly, when j = 0, text2[] is an empty string, and the length of its longest common subsequence with any string is 0, so dp[i][0] = 0. Since the size of the two-dimensional array is deliberately increased by 1, namely m+1 and n+1, and the default value is 0, no further initialization assignment is needed.
When text1[i−1] = text2[j−1], call these two identical characters the common character. Consider the longest common subsequence of text1[0:i−1] and text2[0:j−1]; adding one more character (the common character) gives the longest common subsequence of text1[0:i] and text2[0:j], so dp[i][j]=dp[i−1][j−1]+1. When text1[i−1] != text2[j−1], the longest common subsequence must be obtained from text[0:i-1], text2[0:j] or text[0:i], text2[0:j-1]. That is, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Therefore, the state transition equation is as follows:

{{< katex display >}} dp[i][j] = \left{\begin{matrix}dp[i-1][j-1]+1 &,text1[i-1]=text2[j-1]\max(dp[i-1][j],dp[i][j-1])&,text1[i-1]\neq text2[j-1]\end{matrix}\right. {{< /katex >}}
The final result is stored in dp[len(text1)][len(text2)]. The time complexity is O(mn), and the space complexity is O(mn), where m and n are the lengths of text1 and text2 respectively.

Code

package leetcode

func longestCommonSubsequence(text1 string, text2 string) int {
	if len(text1) == 0 || len(text2) == 0 {
		return 0
	}
	dp := make([][]int, len(text1)+1)
	for i := range dp {
		dp[i] = make([]int, len(text2)+1)
	}
	for i := 1; i < len(text1)+1; i++ {
		for j := 1; j < len(text2)+1; j++ {
			if text1[i-1] == text2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 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
}