描述
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:
1 | Input: text1 = "abcde", text2 = "ace" |
Example 2:
1 | Input: text1 = "abc", text2 = "abc" |
Example 3:
1 | Input: text1 = "abc", text2 = "def" |
Constraints:
1 <= text1.length, text2.length <= 1000
text1
andtext2
consist of only lowercase English characters.
分析
dp[i][j]
表示 text1 的前 i 个字符和 text2 的前 j 个字符,当 text1[i-1]==text2[j-1]
, dp[i][j]=dp[i-1][j-1]+1
, 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
解决方案1(Python)
1 | class Solution: |
解决方案2(Golang)
1 | func longestCommonSubsequence(text1 string, text2 string) int { |
相关问题
- (M) Longest Palindromic Subsequence
- (M) Delete Operation for Two Strings
- (H) Shortest Common Supersequence