最长公共子串

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。 

数据范围： 1 \le |str1|,|str2| \le 50001≤∣str1∣,∣str2∣≤5000
要求： 空间复杂度 O(n^2)O(n2)，时间复杂度 O(n^2)O(n2)

示例1

输入：

"1AB2345CD","12345EF"

复制返回值：

"2345"

复制

备注：

1 \leq |str_1|, |str_2| \leq 5\,0001≤∣str1​∣,∣str2​∣≤5000

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();
    }
}