题解 | #最长公共子串#

记录dp数组中最大值及坐标，然后记录其左上的所有字符即可

class Solution {
public:
    string LCS(string str1, string str2) {
        string res;
        int sz1 = str1.size();
        int sz2 = str2.size();
        int _max = 0, x;
        vector<vector<int>> dp(sz1 + 1, vector<int>(sz2 + 2));
        // 动态规划
        for (int i = 1; i <= sz1; ++i) 
            for(int j = 1; j <= sz2; ++j) 
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if (_max < dp[i][j]) {
                        x = i - 1;  // str1 最大时坐标
                        _max = dp[i][j];
                    }
                }
                else
                    dp[i][j] = 0;
        // 输出字符
        while (_max > 0) {
            res.push_back(str1[x - _max + 1]);
            --_max;
        }
        return res;
    }
};