Longest Common Subsequence

Description

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Example:

For"ABCD"and"EDCA", the_LCS_is"A"(or"D","C"), return1.

For"ABCD"and"EACB", the_LCS_is"AC", return2.

Discussion

Method

DP 匹配

    int longestCommonSubsequence(string A, string B) {
        // write your code here
        vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));

        for(int a_idx = 1; a_idx <= A.size(); ++a_idx) {
            for(int b_idx = 1; b_idx <= B.size(); ++b_idx) {
                if(A[a_idx - 1] == B[b_idx - 1]) {
                    dp[a_idx][b_idx] = dp[a_idx - 1][b_idx - 1] + 1;
                }
                else {
                    dp[a_idx][b_idx] = max(dp[a_idx][b_idx - 1], dp[a_idx - 1][b_idx]);
                }
            }
        }

        return dp[A.size()][B.size()];
    }