# Longest Common Subsequence

## Question

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

Your code should return the length of LCS.

Have you met this question in a real interview? Yes
Example
For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

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

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


## 题解

### Python

class Solution:
"""
@param A, B: Two strings.
@return: The length of longest common subsequence of A and B.
"""
def longestCommonSubsequence(self, A, B):
if not A or not B:
return 0

lenA, lenB = len(A), len(B)
lcs = [[0 for i in xrange(1 + lenA)] for j in xrange(1 + lenB)]

for i in xrange(1, 1 + lenA):
for j in xrange(1, 1 + lenB):
if A[i - 1] == B[j - 1]:
lcs[i][j] = 1 + lcs[i - 1][j - 1]
else:
lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1])
return lcs[lenA][lenB]


### C++

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) {
if (A.empty()) return 0;
if (B.empty()) return 0;

int lenA = A.size();
int lenB = B.size();
vector<vector<int> > lcs = \
vector<vector<int> >(1 + lenA, vector<int>(1 + lenB));

for (int i = 1; i < 1 + lenA; i++) {
for (int j = 1; j < 1 + lenB; j++) {
if (A[i - 1] == B[j - 1]) {
lcs[i][j] = 1 + lcs[i - 1][j - 1];
} else {
lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
}
}
}

return lcs[lenA][lenB];
}
};


### Java

 public class Solution {
/**
* @param A, B: Two strings.
* @return: The length of longest common subsequence of A and B.
*/
public int longestCommonSubsequence(String A, String B) {
if (A == null || A.length() == 0) return 0;
if (B == null || B.length() == 0) return 0;

int lenA = A.length();
int lenB = B.length();
int[][] lcs = new int[1 + lenA][1 + lenB];

for (int i = 1; i < 1 + lenA; i++) {
for (int j = 1; j < 1 + lenB; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
lcs[i][j] = 1 + lcs[i - 1][j - 1];
} else {
lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
}
}
}

return lcs[lenA][lenB];
}
}