题解 | #最长公共子串#

思路： 分析该问题可以发现问题的解即最长公共子串具有一个特点，那就是若子串a₁a₂a₃a₄a₅，是最长公共子串，则a去掉最后一个字符a₅应该是以a₄结尾的最长子串，也就是说最终问题的解包含子问题的解，具有最优子结构，所以可以用动态规划法解决。用cnt[i][j]代表以str1的第i个，str2的第j个结尾的最长公共子串的长度（从1开始计数）。之后寻找当前结果与前一个结果的关系，若当前字符相等，则cnt[i][j]=cnt[i-1][j-1]+1；否则cnt[i][j]=0。边界条件是若选择0个，则公共子串的长度为0。

实现上述思路后进行空间优化，因为以当前字符结束的最长公共子串和原二维数组的左上角元素有关，所以内循环中需要倒序。

注意： 题解中有一个很巧妙的点，后面做题时也能用到，若不能确定当前子串是否为最长子串，如果不停地将子串赋值给结果，会带来很大的空间损耗，所以可以只记录当前为止最大子串的结束位置，以及对应长度，这样循环结束后再赋值，可以节省时间和空间。

代码：

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.length()==0||str2.length()==0){
            return "";
        }
        int len1=str1.length();
        int len2=str2.length();
        int[] cnt=new int[len2+1];//长度其实无所谓，选哪个的长度创建数组，就确保改长度对
        //应的字符串位于内循环中即可
        char[] ss1=str1.toCharArray();
        char[] ss2=str2.toCharArray();
        int maxLen=0;
        int end=0;
        String res=new String();
        for(int i=1;i<=len1;i++){
            char c=ss1[i-1];
            for(int j=len2;j>0;j--){
                //因为以当前字符结束的最长公共子串和原二维数组的左上角元素有关，所以内循环中
                //需要倒序
                if(c==ss2[j-1]){
                    cnt[j]=cnt[j-1]+1;
                    if(cnt[j]>maxLen){
                        end=j;
                        maxLen=cnt[j];
                    }
                }else{
                    cnt[j]=0;
                }
            }
        }
        res=str2.substring(end-maxLen,end);
        return res;
        
//         //正常的动归思路
//         if(str1==null||str2==null||str1.length()==0||str2.length()==0){
//             return "";
//         }
//         int len1=str1.length();
//         int len2=str2.length();
//         int[][] cnt=new int[len1+1][len2+1];
//         char[] ss1=str1.toCharArray();
//         char[] ss2=str2.toCharArray();
//         int maxLen=0;
//         int end=0;
//         String res=new String();
//         for(int i=1;i<=len1;i++){
//             for(int j=1;j<=len2;j++){
//                 if(ss1[i-1]==ss2[j-1]){
//                     cnt[i][j]=cnt[i-1][j-1]+1;
//                     if(cnt[i][j]>maxLen){
//                         maxLen=cnt[i][j];
//                         end=i;
//                     }
//                 }else{
//                     cnt[i][j]=0;
//                 }
//             }
//         }
//         res=str1.substring(end-maxLen,end);
//         return res;
        
    }
}