题解 | 最长公共子串

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[][] dp=new int[str1.length()][str2.length()];
       int max = 0;
       int index =0;
       for(int i=0;i<str1.length();i++){
           for(int j=0;j<str2.length();j++){
              if(str1.charAt(i)==str2.charAt(j)){
                 if(i<1||j<1){
                    dp[i][j]=1;
                 }else{
                       dp[i][j]=dp[i-1][j-1]+1;
                 }
              } else{
                dp[i][j]=0;
              }
               if(dp[i][j]>max){
                max=dp[i][j]; 
                index=i;
               }
           }
       }
        return str1.substring(index-max+1,index+1);
    }
}

动态规划，用矩阵列出相同字符的位置；只可意会，不可言传。