[LintCode] Longest Common Subsequence

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

Your code should return the length of LCS.

Example

For "ABCD" and "EDCA", the LCS is "A" (or D or C), return 1

For "ABCD" and "EACB", the LCS is "AC", return 2

Clarification

What's the definition of Longest Common Subsequence?

    * The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). (Note that a subsequence is different from a substring, for the terms of the former need not be consecutive terms of the original sequence.) It is a classic computer science problem, the basis of file comparison programs such as diff, and has applications in bioinformatics.

    * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

class Solution {
public:
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    int longestCommonSubsequence(string A, string B) {
        // write your code here
        int m = A.length(), n = B.length();
        vector<vector<int>> D(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])
                {
                    D[i][j] = D[i-1][j-1] + 1;
                }
                else
                {
                    D[i][j] = max(D[i][j-1], D[i-1][j]);
                }
            }
        }
        return D[m][n];
    }
};