一今豆、題目
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?
YesExample
For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.
For "ABCD" and "EACB", the LCS is "AC", return 2.
**Notice that the subsequence may be discontinuous in these original sequences.
二、解題思路
求『最長(zhǎng)』類的題目往往與動(dòng)態(tài)規(guī)劃有點(diǎn)關(guān)系，這里是兩個(gè)字符串猜拾，故應(yīng)為雙序列動(dòng)態(tài)規(guī)劃。比較基礎(chǔ)的題。
以 f[i][j] 表示字符串 A 的前 i 位和字符串 B 的前 j 位的最長(zhǎng)公共子序列數(shù)目。
若 A[i] == B[j], 則分別去掉這兩個(gè)字符后娜氏，原 LCS 數(shù)目減一。所以在 A[i] == B[j] 時(shí) LCS 最多只能增加1墩新。即：f[i][j] = f[i-1][j-1]+1贸弥。
而在 A[i] != B[j] 時(shí)，由于
A[i]或者B[j]不可能同時(shí)出現(xiàn)在最終的 LCS 中海渊，故這個(gè)問(wèn)題可進(jìn)一步縮小绵疲， f[i][j] = max(f[i - 1][j], f[i][j - 1]) .
三、解題代碼
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];
}
}
下一篇: 3. DP_Lintcode76 最長(zhǎng)增長(zhǎng)(上升)子序列Longest Increasing Subsequence solution
上一篇: 1. DP_LeetCode114. Distinct Subsequences
