LCS (Lintcode 79 & Lintcode 77)

总结两道LCS问题

(1). Longest Common Sub-sequence(Lintcode 77)
(2). Longest Common Sub-string(Lintcode 79);

1. 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];
        
    }

2. 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];
    }