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

Your code should return the length ofLCS.

Have you met this question in a real interview?

Yes

Clarification

What's the definition of Longest Common Subsequence?

• https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
• http://baike.baidu.com/view/2020307.htm

Example

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

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

line 19 should add 1

check after writing every lines

in the end check each line again , condition , variable

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 lcs\[A.length\(\) + 1\]\[B.length\(\) + 1\];

    for \(int i = 0; i <= A.length\(\); ++i\) {

        lcs\[i\]\[0\] = 0;

    }

    for \(int i = 0; i <= B.length\(\); ++i\) {

        lcs\[0\]\[i\] = 0;

    }

    for \(int i = 1; i <= A.length\(\); ++i\) {

        for \(int j = 1; j <= B.length\(\); ++j\) {

            if \(A\[i - 1\] == B\[j - 1\]\) {

                lcs\[i\]\[j\] = lcs\[i - 1\]\[j - 1\] + 1;

            } else {

                lcs\[i\]\[j\] = max\(lcs\[i - 1\]\[j\], lcs\[i\]\[j - 1\]\);

            }

        }

    }



    return lcs\[A.length\(\)\]\[B.length\(\)\];

}

};