1143. 最长公共子序列

1143. 最长公共子序列

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

思路分析

动态规划的最长公共子序列模板题目。设定dp[i] [j]表示两个字符串前i个字符和前j个字符的最长公共子序列，那么当text1[i]==text2[j]的时候，就等于dp[i] [j]=dp[i-1] [j-1]+1，当不相等的时候，那么dp[i] [j]=max(dp[i-1] [j],dp[i] [j-1]);本题中为了方便讨论边界，计算dp[i] [j]的时候比较的是第i-1个字符和第j-1个字符，否则在计算dp[0] [0] 和dp[0] [1] 和dp[1] [0]会越界。

代码实现

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1=text1.size();
        int len2=text2.size();
        vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));

        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;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[len1][len2];
    }
};

1143. 最长公共子序列

原文：https://www.cnblogs.com/zengfanlu/p/14888870.html