题解 | #最长公共子串#

方法一：动态规划

1、使用一个二维数组dp记录两个字符串不同位置结尾的公共子串长度，状态转移方程如下：

字符相等时：dp[i][j] = 1 + dp[i - 1][j - 1]

字符不相等时：dp[i][j] = 0

2、在遍历不同位置的同时，记录下最长的公共子串长度以及结尾的序号，可以得到最长的公共子串

时间复杂度：o(n²)

空间复杂度：o(n²)

class Solution {
  public:
    string LCS(string str1, string str2) {
        vector<vector<int> > dp(str1.length() + 1, vector<int> (str2.length() + 1, 0));
        int max_len = 0;
        int idx = 0;
        string res = "";
        // 记录两个字符串以不同位置结尾的最长公共子串长度
        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] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 0;
                }
                // 记录下最长的公共子串长度和str1的结尾序号
                if (dp[i][j] > max_len) {
                    max_len = dp[i][j];
                    idx = i - 1;
                }
            }
        }
        // 输出最长公共子串
        for (int i = idx - max_len + 1; i <= idx; i++)
            res += str1[i];

        return res;
    }
};

方法二：枚举

1、遍历两个字符串的不同位置，以不同位置作为起点计算公共子 串长度；

2、在遍历不同位置的同时，记录下最长的公共子串长度以及结尾的序号，可以得到最长的公共子串

时间复杂度相比动态规划较高

时间复杂度：o(m²n)，m为str2的长度，n为str1的长度。

空间复杂度：o(n)

class Solution {
  public:
    string LCS(string str1, string str2) {
        int max_len = 0;
        string max_str = "";

        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                string res = "";
                int str_len = 0;
                int temp_i = i, temp_j = j;
                // 遍历所有的位置为起始点，寻找最长的公共子串
                while (temp_i < str1.length() && temp_j < str2.length() &&
                        str1[temp_i] == str2[temp_j]) {
                    res += str1[temp_i];
                    temp_i++;
                    temp_j++;
                    str_len++;
                }
                if (str_len > max_len) {
                    max_len = str_len;
                    max_str = res;
                }
            }
        }

        return max_str;
    }
};