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.

Examples

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.

题目分析

Dynamic Programming

代码实现

const int N = 1e3 + 10;
class Solution {
public:
    int dp[N][N], n, m;
    int longestCommonSubsequence(string s1, string s2) {
        n = s1.length(), m = s2.length();
        dp[0][0] = s1[0] == s2[0];
        for(int i = 1; i < n; ++i) dp[i][0] = dp[i - 1][0] | (s1[i] == s2[0]);
        for(int j = 1; j < m; ++j) dp[0][j] = dp[0][j - 1] | (s1[0] == s2[j]);
        for(int i = 1; i < n; ++i) {
            for(int j = 1; j < m; ++j) {
                if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n - 1][m - 1];
    }
};
分类: DP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status