Longest Common Subsequence

Description

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

Your code should return the length of LCS. Clarification:
What's the definition of Longest Common Subsequence?
wiki LCS
baidu LCS

Example
For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.
For "ABCD" and "EACB", the LCS is "AC", return 2.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    int longestCommonSubsequence(string s1, string s2) {
        // write your code here
         // write your code here
        if (s1.empty() || s2.empty()) {
            return 0;
        }
        int n1 = s1.size();
        int n2 = s2.size();
        vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                // // dp[abcd][uvwx] = max(dp[abc][uvwx], dp[abcd][uvw])
                // dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                // // if the last letter is the same
                // if (s1[i-1] == s2[j-1]) {
                //     dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
                // }
                // if the last letter is not the same
                // dp[abcd][uvwx] = max(dp[abc][uvwx], dp[abcd][uvw])
                if (s1[i-1] != s2[j-1]) {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                } else {
                // if the last letter is the same
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
                }
            }
        }
        return dp[n1][n2];
    }
};

Similar problems

x

Tags

x