题解 | #最长公共子串#

第二种：动态规划
思路： 二维数组， 下图：str1: sabgc ,s2:abcg, 二维数组，相同的标记为1 ，不同的标0，可以看出斜对角为1 的就是最长的字串。第一个一样标记1， 第二个对角相同，值应该是x,y下标-1 的值在+1，记录的就是长度。

为了让递推公式dp[i][j] = dp[i-1][j-1] + 1;成立,所以应多初始化一行一列dp[0][0],相当于在图片外层又包裹一行一列的0

红色部分为新增的一行一列的初始化dp
黄色部分为数组下标偏移1位
这样在推到dp[1][0]的时候 就可以通过刚刚新增的dp初始化红色部分数组的值0,来推出其值为左上角位置+1

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) {

        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) {
            return "-1";
        }

        //动态规划  二维数组，斜下来就是最长字串
        int str1Len = str1.length();

        int str2Len = str2.length();

        //记录最长公共子串长度
        int maxLen = 0;

        //记录最长子串最后一个字符的下标
        int index = 0;

        //这里+1 是为了让dp[i][j] = dp[i-1][j-1] + 1;递推公式成立,单独多出一行一列dp[0][0]供递推公式计算
        int[][] dp = new int[str1Len + 1][str2Len + 1];

        //str1为行坐标
        for (int i = 1; i <= str1Len; i++) {

            //str2为列坐标
            for (int j = 1; j <= str2Len; j++) {

                //这里的i-1 j-1意味着是字符串的第一个字符,而非dp[0][0]这个第一列
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                   //str1 str2的该位置字符如果相等,那么用上一个斜上角位置的元素进行+1 可获取当前公共子串的长度
                   dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = 0;
                }

                if (maxLen < dp[i][j]) {
                    maxLen = dp[i][j];
                    //因为不能算dp[0] 所以以上循环都是从1开始的 这里要减去1
                    index = i-1;
                }
            }
        }

        if (maxLen == 0) {
            return "-1";
        }

        return str1.substring(index - maxLen + 1, index + 1);
    }
}