美文网首页
LintCode 77. Longest Common Subs

LintCode 77. Longest Common Subs

作者: xingzai | 来源:发表于2019-07-23 12:10 被阅读0次

    题目链接

    Description
      Given two strings, find the longest common subsequence (LCS).
    Your code should return the length of LCS.

    Example 1:

    Input: "ABCD" and "EDCA"
    Output: 1
    Explanation:
    LCS is 'A' or 'D' or 'C'

    Example 2:

    Input: "ABCD" and "EACB"
    Output: 2
    Explanation:
    LCS is "AC"

    思路:
      这是一个经典的动态规划题,定义dp矩阵,dp[i][j]表示A串匹配到i,B串匹配到j时的最大公共长度。dp有A.length()+1行,有B.length()列。第一行与第一列都为0;
    有状态转移方程:


    最后返回dp的最大值即为最长公共子串长度,代码如下:
    class Solution {
    public:
        /**
         * @param A: A string
         * @param B: A string
         * @return: The length of longest common subsequence of A and B
         */
        int longestCommonSubsequence(string &A, string &B) {
            // write your code here
            int m = A.size(), n = B.size();
            if (m == 0 || n==0) return 0;
            //int dp[m+1][n+1];
            std::vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
            for (int i=1; i<=m; ++i) {
                for (int j=1; j<=n; ++j) {
                    if (A[i-1] == B[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[m][n];
        }
    };
    

    类似题目:

    相关文章

      网友评论

          本文标题:LintCode 77. Longest Common Subs

          本文链接:https://www.haomeiwen.com/subject/hvjolctx.html