[LintCode]最長共通サブシーケンス
3267 ワード
1 class Solution {
2 public:
3 /**
4 * @param A, B: Two strings.
5 * @return: The length of longest common subsequence of A and B.
6 */
7 int longestCommonSubsequence(string A, string B) {
8 // write your code here
9 int m = A.length(), n = B.length();
10 vector<int> cur(m + 1, 0);
11 for (int j = 1; j <= m; j++) {
12 int pre = 0;
13 for (int i = 1; i <= m; i++) {
14 int temp = cur[i];
15 cur[i] = (A[i - 1] == B[j - 1]) ? pre + 1 : max(cur[i], cur[i - 1]);
16 pre = temp;
17 }
18 }
19 return cur[m];
20 }
21 };