题解 | #最长公共子串#

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
        int[][] mat =  new int[str1.length() + 1][str2.length() + 1];
        int maxLen = 0;
        int lastIdx = 0;
        for(int i = 1; i < mat.length; i++) {
            for(int j = 1; j < mat[0].length; j++) {
                if(str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    mat[i][j] = mat[i - 1][j - 1] + 1;
                    if(mat[i][j] > maxLen) {
                        maxLen = mat[i][j];
                        lastIdx = i;
                    }
                } else {
                    mat[i][j] = 0;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int j = lastIdx - maxLen; j < lastIdx; j++) {
            sb.append(str1.charAt(j));
        }
        return sb.toString();
    }
}