题解 | #最长公共子串#

一.题目描述
给定两个字符串str1和str2,输出两个字符串的最长公共子串，题目保证str1和str2的最长公共子串存在且唯一。
二.算法(java实现动态规划)
图片说明
dp[i][j]表示字符串1的以i结尾的字符串，字符串2的以j结尾的公共子串
当str1[i]==str2[j],dp[i][j]等于dp[i-1][j-1]+1;
当str1[i]!=str2[j]时,dp[i][j]=0,由于是连续的，如果此时不要求连续子串

下面是完整代码：

import java.util.*;


public class Solution {
    /**
    需要添加maxindex来记录最后的返回字符串
     */
   public String LCS(String str1, String str2) {
    int maxlen=0,maxindex = 0;
    //maxlen记录最长公共子串的长度
    //maxidex记录最长公共子串最后一个元素在字符串str1中的位置
    int[][] dp = new int[str1.length() + 1][str2.length() + 1];
    for (int i = 0; i < str1.length(); i++) {
        for (int j = 0; j < str2.length(); j++) {
            //状态转移，两个字符相等的情况
            if (str1.charAt(i) == str2.charAt(j)) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                //如果遇到了更长的子串，要更新，记录最长子串的长度，
                //以及最长子串最后一个元素的位置
                if (dp[i+1][j+1] > maxlen) {
                    maxlen=dp[i+1][j+1];
                    maxindex = i;
                }
            } else {
                dp[i+1][j+1] = 0;
            }
        }
    }
    //对字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
    return str1.substring(maxindex-maxlen+1, maxindex+1);
}
}

时间复杂度： $O(n*m)$ 其中n,m分别表示str1,str2的长度
空间复杂度： $O(n*m)$ 需要额外开辟空间进行公共字符串长度存储
优缺点：便于实现，但是空间利用率不高
三.算法(java进行空间优化)
考虑到dp[i][j]仅与dp[i-1][j-1]有关，所以可以把二维状态压缩为一维,思路算法二一样，但是利用一维数组进行了优化，提高了空间利用率。下面是完整代码：

import java.util.*;


public class Solution {
    public String LCS (String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[] dp = new int[len2 + 1];
        int maxlen = 0;
        int end = 0;
        //maxlen表示最长的公共字符串长度
        //end表示最后最长公共字符串最后一位的下表
        for (int i = 1; i <= len1; i ++) {
            for(int j = len2; j >= 1; j --) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {     
                    dp[j] = dp[j-1] + 1;
                    int t = maxlen;
                    maxlen = Math.max(maxlen, dp[j]);
                    if (maxlen > t) {
                        end = i;
                    }
                } else {
                    dp[j] = 0;
                }
            }
        }
        //同样利用substring返回最后的字符串
        return str1.substring(end - maxlen, end);
    }
}

时间复杂度： $O(n*m)$ 其中n,m分别表示str1,str2的长度
空间复杂度： $O(m)$ 需要额外开辟空间进行公共字符串长度存储
优缺点：便于实现，而且空间利用率高