总结两道LCS问题
(1). Longest Common Sub-sequence(Lintcode 77)
(2). Longest Common Sub-string(Lintcode 79);
- Longest Common Sub-sequence问题
sub-squence问题是，sub-sequence并不要求连续。状态方程建立为前 i 个，与前 j 个的比较。
所以当前点dp[i][j] 是等于 dp[i-1][j] and dp[i][j-1] 的max。同时，如果s[i-1] == s[j-1], dp[i][j]， 还需要比较dp[i-1][j-1]+1。
可以举几个word矩阵的例子，推导出状态转移方程。
a, b, c
0, 0, 0, 0
a, 1, 1, 1
c, 1, 1, 2
d, 1, 1, 2
代码如下：
int longestCommonSubsequence(string A, string B) {
// write your code here
if(A.empty() || B.empty()) return 0;
int lenA = A.length(), lenB = B.length();
vector<vector<int>> dp(lenA+1, vector<int>(lenB+1, 0));
for(int i=1; i<=lenA; i++){
for(int j=1; j<=lenB; j++){
if(A[i-1] == B[j-1]){
dp[i][j] = max(dp[i-1][j-1]+1, max(dp[i-1][j], dp[i][j-1]));
}else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[lenA][lenB];
}
};
或者更简化：
int longestCommonSubsequence(string &A, string &B) {
// write your code here
if(A.empty() || B.empty()) return 0;
int lenA = A.size(), lenB = B.size();
vector<vector<int>> dp(lenA+1, vector<int>(lenB+1, 0));
for(int i=1; i<=lenA; i++){
for(int j=1; j<=lenB; j++){
if(A[i-1] == B[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[lenA][lenB];
}
- Longest Common Sub-string问题
这道题 sub-string要求连续，需要进行变换。状态建立为第 i 个，与第 j 个的比较。所以，dp[i][j] 是要以i，j为结尾的sub-string是否相等。相等存常数，不等直接为0。
同时，并不返回 dp[lenA][lenB]， 而是建立一个随时update 的max_len 独立变量，返回这个变量。
int longestCommonSubstring(string &A, string &B) {
// write your code here
if(A.empty() || B.empty()) return 0;
int lenA = A.length(), lenB = B.length();
vector<vector<int>> dp(lenA+1, vector<int>(lenB+1, 0));
int max_len = INT_MIN;
for(int i=1; i<=lenA; i++){
for(int j=1; j<=lenB; j++){
if(A[i-1] == B[j-1]){
dp[i][j] = dp[i-1][j-1]+1;
}else{
dp[i][j] = 0;
}
if(dp[i][j] > max_len) max_len = dp[i][j];
}
}
return max_len;
}
下面是Edit Distance的代码，Edit Distance不同的是要写初始化，而不是直接从0算起。
public int minDistance(String word1, String word2) {
// write your code here
int len1 = word1.length(), len2 = word2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i=0; i<=len1; i++){
dp[i][0] = i;
}
for(int i=0; i<=len2; i++){
dp[0][i] = i;
}
for(int i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){
if(word1.charAt(i-1) == word2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j])) + 1;
}
}
}
return dp[len1][len2];
}
