题解 | #最长公共子串#

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) return "-1";
        int n1 = str1.length(), n2 = str2.length();
        if (n1 == 0 || n2 == 0) return "-1";
        int[][] dp = new int[n1 + 1][n2 + 1];

        int maxLen = 0, x = 0;  //记录最长公共子串的长度  以及结束索引+1
        for (int i = 1; i <= n1; i++) {
            char ch1 = str1.charAt(i - 1);
            for (int j = 1; j <= n2; j++) {
                char ch2 = str2.charAt(j - 1);
                if (ch1 == ch2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        x = i;
                    }
                }
            }
        }

        return maxLen == 0 ? "-1" : str1.substring(x - maxLen, x);
    }


}