题解 | #最长公共子串#

题目主要信息：

• 查找两个字符串str1，str2中的最长的公共子串
• 保证str1和str2的最长公共子串存在且唯一

举一反三：

学习完本题的思路你可以解决如下题目：

BM65 最长公共子序列(二)

BM71.最长上升子序列(一)

BM73 最长回文子串

BM75 编辑距离(一)

BM76 正则表达式匹配

BM77 最长的括号子串

方法一：枚举（前置方法，超时，不能完全通过）

思路：

最简单直观的方式大概就是枚举了，枚举所有的子串进行比较，但是太复杂了。其实找子串不用一样完全枚举，还可以尝试改良一下

具体做法：

• step 1：我们完全可以遍历两个字符串的所有字符串作为起始
• step 2：然后同时开始检查字符是否相等，相等则不断后移，增加子串长度，如果不等说明以这两个为起点的子串截止了，不会再有了。
• step 3：后续比较长度维护最大值即可。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public String LCS (String str1, String str2) {
        int length = 0;
        String res = ""; 
        //遍历s1每个起始点
        for(int i = 0; i < str1.length(); i++){ 
            //遍历s2每个起点
            for(int j = 0; j < str2.length(); j++){ 
                int temp = 0;
                String temps = "";
                int x = i, y = j;
                //比较每个起点为始的子串
                while(x < str1.length() && y < str2.length() && str1.charAt(x) == str2.charAt(y)){ 
                    temps += str1.charAt(x);
                    x++;
                    y++;
                    temp++;
                }
                //更新更大的长度子串
                if(length < temp){ 
                    length = temp;
                    res = temps;
                }
            }
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    string LCS(string str1, string str2) {
        int length = 0;
        string res = ""; 
        //遍历s1每个起始点
        for(int i = 0; i < str1.length(); i++){ 
            //遍历s2每个起点
            for(int j = 0; j < str2.length(); j++){ 
                int temp = 0;
                string temps = "";
                int x = i, y = j;
                //比较每个起点为始的子串
                while(x < str1.length() && y < str2.length() && str1[x] == str2[y]){ 
                    temps += str1[x];
                    x++;
                    y++;
                    temp++;
                }
                //更新更大的长度子串
                if(length < temp){ 
                    length = temp;
                    res = temps;
                }
            }
        }
        return res;
    }
};

Python代码实现：（Python版本不超时）

class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        #让str1为较长的字符串
        if len(str1) < len(str2): 
            str1, str2 = str2, str1
        res = ''
        max_len = 0
        #遍历str1的长度
        for i in range(len(str1)): 
            #查找是否存在
            if str1[i - max_len : i + 1] in str2: 
                res = str1[i - max_len : i + 1]
                max_len += 1
        return res

复杂度分析：

• 时间复杂度：$O(m^{2}n)O(m^2n)$，其中$mm$是str1的长度，$nn$是str2的长度，分别枚举两个字符串每个字符作为起点，后续检查子串长度最坏需要花费$O(m)O(m)$
• 空间复杂度：$O(n)O(n)$，res属于返回必要空间，temps属于临时辅助空间，最坏情况下长度为$nn$

方法二：动态规划（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

思路：

动态规划继承自方法一，在枚举的基础上用动态规划来改进。

具体做法：

• step 1：我们可以用$dp[i][j]dp[i][j]$表示在str1中以第$ii$个字符结尾在str2中以第$jj$个字符结尾时的公共子串长度，
• step 2：遍历两个字符串填充dp数组，转移方程为：如果遍历到的该位两个字符相等，则此时长度等于两个前一位长度+1，$dp[i][j]=dp[i-1][j-1]+1dp[i][j]\; =\; dp[i\; -\; 1][j\; -\; 1]\; +\; 1$，如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。
• step 3：每次更新$dp[i][j]dp[i][j]$后，我们维护最大值，并更新该子串结束位置。
• step 4：最后根据最大值结束位置即可截取出子串。

Java实现代码：

import java.util.*;
public class Solution {
    public String LCS (String str1, String str2) {
        //dp[i][j]表示到str1第i个个到str2第j个为止的公共子串长度
        int[][] dp = new int[str1.length() + 1][str2.length() + 1]; 
        int max = 0;
        int pos = 0;
        for(int i = 1; i <= str1.length(); i++){
            for(int j = 1; j <= str2.length(); j++){
                //如果该两位相同
                if(str1.charAt(i - 1) == str2.charAt(j - 1)) 
                    //则增加长度
                    dp[i][j] = dp[i - 1][j - 1] + 1; 
                else 
                    //该位置为0
                    dp[i][j] = 0; 
                //更新最大长度
                if(dp[i][j] > max){ 
                    max = dp[i][j];
                    pos = i - 1;
                }
            }
        }
        return str1.substring(pos - max + 1, pos + 1);
    }
}

C++实现代码：

class Solution {
public:
    string LCS(string str1, string str2) {
        //dp[i][j]表示到str1第i个个到str2第j个为止的公共子串长度
        vector<vector<int> > dp(str1.length() + 1, vector<int>(str2.length() + 1, 0)); 
        int max = 0;
        int pos = 0;
        for(int i = 1; i <= str1.length(); i++){
            for(int j = 1; j <= str2.length(); j++){
                //如果该两位相同
                if(str1[i - 1] == str2[j - 1]){ 
                    //则增加长度
                    dp[i][j] = dp[i - 1][j - 1] + 1; 
                }
                else{ 
                    //该位置为0
                    dp[i][j] = 0; 
                }
                //更新最大长度
                if(dp[i][j] > max){ 
                    max = dp[i][j];
                    pos = i - 1;
                }
            }
        }
        return str1.substr(pos - max + 1, max);
    }
};

Python代码实现：（Python版本超时，不能完全通过）

class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        #dp[i][j]表示到str1第i个个到str2第j个为止的公共子串长度
        dp = [[0] * (len(str2) + 1) for i in range(len(str1) + 1)]
        max = 0
        pos = 0
        for i in range(1, len(str1) + 1):
            for j in range(1, len(str2) + 1):
                #如果该两位相同
                if str1[i - 1] == str2[j - 1]: 
                    #则增加长度
                    dp[i][j] = dp[i - 1][j - 1] + 1 
                else: 
                    #该位置为0
                    dp[i][j] = 0 
                #更新最大长度
                if dp[i][j] > max: 
                    max = dp[i][j]
                    pos = i - 1
        return str1[pos - max + 1: pos + 1]

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，其中$mm$是str1的长度，$nn$是str2的长度，遍历两个字符串所有字符
• 空间复杂度：$O(mn)O(mn)$，dp数组大小为$m\ast nm*n$