Longest Common Subsequence and substring

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? YesProblem Correction

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

Example

For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

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

注意在双层for循环内，i和j对应的是数组的位置，是从1开始的，在定位string index的时候 应该减去1

public class Solution {
    /**
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        
        if(A == null || A.length() == 0 || B == null || B.length() == 0){
            return 0;
        }
        
        int lenA = A.length();
        
        int lenB = B.length();
        
        int[][] dp = new int[lenA+1][lenB+1];
        
        //
        
        for (int i = 0;i<= lenA ; i++){
            dp[i][0] = 0;
        } 
        
        for(int i = 0; i <= lenB ;i++){
            dp[0][i] = 0;
        }
        
        for(int i = 1; i <=lenA;i++){
            for(int j= 1; j<= lenB;j++){
                if(A.charAt(i-1) == B.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        
        return dp[lenA][lenB];
    }
}

Longest command substring

substring和subsequence 的 区别就是 substring不能中断，subsequence可以中断，任意组合都可以，所以在longest comman substring里，如果对比字符不一样的话，就是0，一样的话就是对角线上一个加1，但是longest common subsquence就不一样了，如果当前字符相同，同样是对角线加1，如果不相同，取上或者左 最大的加一

public int LongestCommonSubstring(String A, String B){
    if(A == null || B == null || A.length() == 0 || B.length() == 0) return 0;
    
    int n1 = A.length();
    
    int n2 = B.length();
    //dp[i][j] means the total common substring 
    // length  between A substring  0 - i and B substring 0-j;
    int[][] dp = new int[n1+1][n2+1];
    
    for(int i = 0; i <= n1;i++){
        dp[i][0] = 0;
    }
    
    for(int i = 0; i <= n2; i++){
        dp[0][i] = 0;
    }
    int res;
    for(int i = 1; i <= n1; i++){
        for(int j = 1; j <= n2; j++){
            if(A.charAt(i-1) == B.charAt(j-1)){
                dp[i][j] = dp[i-1][j-1] + 1;
                res = Math.max(dp[i][j],res);
            }else{
                dp[i][j] = 0;
            }
        }
    }
    
    return res;
}