题解 | 最长公共子串

dp[i][j]表示在str1中以i结尾，在str2中以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
        StringBuilder res = new StringBuilder();

        int[][] dp = new
        int[str1.length()][str2.length()];//dp[i][j]表示str1以i结尾，str2以j结尾时的最长公共子串长度
        //(公共最长子串在str1中以i结尾，在str2中以j结尾)
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) == str2.charAt(0)) dp[i][0] = 1;
            else dp[i][0] = 0;
        }
        for (int j = 0; j < str2.length(); j++) {
            if (str1.charAt(0) == str2.charAt(j)) dp[0][j] = 1;
            else dp[0][j] = 0;
        }
        int maxLen = 0;
        int maxLenEndInStr1 = 0;
        for (int i = 1; i < str1.length(); i++) {
            for (int j = 1; j < str2.length(); j++) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        maxLenEndInStr1 = i;
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        if (maxLen == 0)return"";
        else return str1.substring(maxLenEndInStr1 - maxLen + 1, maxLenEndInStr1 + 1);
    }
}