> For the complete documentation index, see [llms.txt](https://shuati.gitbook.io/crack-lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shuati.gitbook.io/crack-lintcode/linkedin/longest-common-subsequence.md).

# 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`.

{% embed url="<https://www.youtube.com/watch?v=HgUOWB0StNE>" %}

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

```java
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

&#x20;substring和subsequence 的 区别就是

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

```java
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;
}
```