最长公共子串

这个 dp 注意一个点 最长子串 和 最长子序列 是不同的概念 最长子串 是需要连续的 所以下一个
dp 的计算只与斜角有关 即 只考虑 包括当前位的当前最长子串 如果当前位不相等 即 str1[i]!=str2[j] 则 dp[i][j]=-1
之前是 dp 直接存 String 结果 超时 所以参考优化了一下改成记录最大长度及开始位置

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
       if(str1 == null || str2 == null || str1.equals("") || str2.equals("")){
            return "-1";
        }
        char[] cstr1=str1.toCharArray();
        char[] cstr2=str2.toCharArray();
        int N1=cstr1.length;
        int N2=cstr2.length;
        int [][] dp=new int[N1][N2];
        int max=0;
        int indexMax=0;
        if(cstr1[0]==cstr2[0]){
            dp[0][0]=1;
            max=1;
        }else{
            dp[0][0]=-1;
        }

        //初始化列表边界
        for(int i=1;i<N1;i++){
            if (cstr1[i]==cstr2[0]){
                dp[i][0]=1;

            }else {
                dp[i][0]=-1;
            }


        }
        //初始化行边界
        for(int i=1;i<N2;i++){

            if (cstr2[i]==cstr1[0]){
                dp[0][i]=1;
                max=1;
            }else {
                dp[0][i]=-1;
            }

        }

        //任何一个位置的普遍公式
        //末位最近最长子序列
        for(int i=1;i<N1;i++){
            for(int j=1;j<N2;j++){
                if(cstr1[i]==cstr2[j]){
                    dp[i][j]=(dp[i-1][j-1]==-1?0:dp[i-1][j-1])+1;
                }else{
                    dp[i][j]=-1;
                }
                if(dp[i][j]!=-1){
                    if (dp[i][j]>=max){
                        max=dp[i][j];
                        indexMax=i;
                    }
                }
            }
        }
        if (max==0){
            return "-1";
        }
        return str1.substring(indexMax-max+1,indexMax+1);
    }
}