1143. Longest Common Subsequence
Medium
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 <= 1000text1andtext2consist of only lowercase English characters.
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++ {
// dp[i][j] = text1 前 i 個字母和 text2 前 j 個字母 最長子序列長
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[len(text1)][len(text2)]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}