题解 | #最长公共子串#

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.length() == 0 || str2.length() == 0) {
            return "-1";
        }

        int len1 = str1.length();
        int len2 = str2.length();
        // 子串要求连续，因此不能简单定义成“str1前i位与str2前j位组成的公共子串最大长度”这种无视连续关系的定义，找不到递推关系
        // 因此，dp[i][j]表示以str1第i个字符和str2第j个字符结尾的最长公共子串长度
        // 初始化-1
        int[][] dp = new int[len1 + 1][len2 + 1];

        // 不用递归尝试了，因为按照这个定义，当字符不相等时，直接赋0，无法进入递归分支
        // 直接双重for循环搞定
        
        // 只需要记录最大长度和str1结尾下标即可，start = end - maxLength
        int maxLength = 0;
        int end = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    // 公共字符，则根据定义，在dp[i-1][j-1]的基础上+1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                // 更新最大值
                if (dp[i][j] > maxLength) {
                    maxLength = dp[i][j];
                    // 注意！end配合substring使用，end是开区间，因此要记录实际下标的后一位，即i-1的后一位i
                    end = i;
                }
            }
        }

        // 截取str1子串并输出
        if (maxLength == 0) {
            // 不存在公共子串，返回"-1"
            return String.valueOf(-1);
        } else {
            // 存在公共子串，返回最大子串
            return str1.substring(end - maxLength, end);
        }
    }
}