题解 | #最长公共子串#TOP66

思路:
1.区别于上一道题，公共子序列，这道题是公共子串
2.利用dp[i][j]记录 str1[0,i-1] 与 str2[0,j-1]的公共子串长度，如果哦str[i-1]== str[j-1]那么 dp[i][j] = dp[i-][j-1] + 1,记录下最大的dp[i][j],再记录此时的下标。遍历结束后，有了公共子串长度和结束位置，不就得出了公共子串么

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        if(str1 == null || str2 == null){
            return null;
        }
        int m = str1.length();
        int n = str2.length();
        //dp[i][j] 代表 0...i-1 到 0....j-1 以 i-1 和 j-1为尾的公共子串长度
        int[][] dp = new int[m+1][n+1];
        //max 最长公共子串长度
        int max = 0,end = 0;
        for(int i = 1;i <= m;i++){
            for(int j = 1;j<= n;j++){
                if(str1.charAt(i-1) == str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if(max < dp[i][j]){
                        max = dp[i][j];
                        end = i - 1;
                    }
                }
            }
        }
        
        return max == 0 ?"-1" : str1.substring(end - max + 1, end+1);
        
    }
}