题解 | #最长公共子串#

暴力方法：遍历两个字符串。时间复杂度大于O(n^2)。

class Solution {
public:
    string LCS(string str1, string str2) {
        int maxn = 0, start = -1;
        for(int i = 0; i < str1.size(); i++) {
            for(int j = 0; j < str2.size(); j++) {
                int cnt = 0;
                while(i+cnt < str1.size() && 
                      j+cnt < str2.size() && 
                      str1[i+cnt] == str2[j+cnt]) 
                    cnt++;
                if(maxn < cnt) {maxn = cnt; start = i;}
            }
        }
        return str1.substr(start, maxn);
    }
};

二维dp数组：时间复杂度O(n^2)，空间复杂度O(n^2)。

class Solution {
public:
    string LCS(string str1, string str2) {
        int maxn = 0, end = 0;
        int m = str1.size(), n = str2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(str1[i-1] == str2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else dp[i][j] = 0;
                if(dp[i][j] > maxn) {
                    end = i; maxn = dp[i][j];
                }
            }
        }
        return str1.substr(end-maxn, maxn);
    }
};

一维dp数组：

class Solution {
public:
    string LCS(string str1, string str2) {
        int maxn = 0, end = 0;
        int m = str1.size(), n = str2.size();
        vector<int> dp(n+1, 0);
        for(int i = 1; i <= m; i++) {
            for(int j = n; j > 0; j--) {
                if(str1[i-1] == str2[j-1]) {
                    dp[j] = dp[j-1] + 1;
                } else dp[j] = 0;
                if(dp[j] > maxn) {
                    end = i; maxn = dp[j];
                }
            }
        }
        return str1.substr(end-maxn, maxn);
    }
};