127 最长公共子串（牛客题霸 ）

方法一：动态规划（此题画出动态变化表更易理解）

原理：类似于力扣：1143. 最长公共子序列
时间复杂度O(n * m) n 为A长度，m为B长度
空间复杂度O(n * m)

逻辑

public static String LCS (String str1, String str2) {
    // write code here
    int dp[][] = new int[str1.length() + 1][str2.length() + 1];
    for (int i = 0; i < dp.length; i++) dp[i][0] = 0;
    for (int i = 0; i < dp[0].length; i++) dp[0][i] = 0;
    int maxLen = 0;    //记录最大长度
    int end = 0;    //字符串截取的末尾后一位
    for (int i = 1; i <= str1.length(); i++) {
        for (int j = 1; j <= str2.length(); j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = 0;
            if (maxLen < dp[i][j]) {
                maxLen = dp[i][j];
                end = j;    //将末尾后一位保存下来
            }
        }
    }
    if (maxLen == 0) return "-1";
        //substring 是左闭右开的
    else return str2.substring(end - maxLen, end);
}