题解 | 最长公共子序列(二)

核心是要明白动态规划数组如何求得，以及后续如何根据数组末尾元素反推得到公共序列路径。

现在我们脑海中构建一个二维数组，这个数组纵轴的坐标代表了s1对应的字符下标，横轴代表s2对应的字符下标。

当然，因为动态规划的初值需要给出，我们将数组第0列和第0行的元素全都设为0，表示当字符串为空时，匹配数目为0。

知道初值以后，我们就可以一步步递推求数组了。

1.求动态规划数组

①在循环遍历时，倘若遇到两个字符串中的字符匹配s1[i]=s2[j],那么记录当前匹配字符数的arr[i+1][j+1]就是其斜上角的arr[i][j]+1。（不要忘了由于我们为了动态规划的初值存储，特地为其腾出了第0行和第0列的空间噢）

*为什么不能从左/上角得到其最大值+1呢？

填写动态规划数组的过程其实就是算从0到当前i,j下标位置s1和s2的匹配字符数，当你填写s1第二个a时，你想要用上方的2再+1填进去？不行噢，s1第一个a告诉你它已经和s2的a匹配了，这个时候你就不能再和其匹配了。否则你岂不是计算出了a和aa的公共子序列是aa了嘛。

②字符不相等s1[i]！=s2[j]时，匹配字符数无变化，那么我们就把先前匹配的最大字符数继承过来，可以从左边或上面取最大值。即arr[i + 1][j + 1] = max(arr[i + 1][j], arr[i][j + 1])

2.回溯路径得到公共序列

由于动态规划求数组有两种解决分支，那么这个回溯有两种思路。

way1 （对应题解1）:可以根据当前arr[i + 1][j + 1] 是否等于 max(arr[i + 1][j], arr[i][j + 1])判断。

如果相等，找出它左/上的最大值，对应下标--，遍历到这个最大值所在的坐标；

如果不等，那么就必然是从斜上角找了，两个下标都--，遍历到斜上角的坐标。

way2 （对应题解2）：根据当前坐标i,j，判断s1[i]是否等于s2[j]。

相等，说明从斜上角找；

不等，从它左/上找。

当进入标红的分支时，说明字符匹配，那么就把这个字符推入栈中。

最后输出栈的内容就好啦。（因为是倒序回溯所以要使用栈）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        int m = s1.length()+1;
        int n = s2.length()+1;
        int** arr = new int* [m];
        for (int i = 0; i < m; i++) {
            arr[i] = new int[n];
        }
        for(int i = 0; i < m; i++) {
            arr[i][0] = 0;
        }
        for (int j = 0; j < n; j++) {
            arr[0][j] = 0;
        }
        for (int i = 0; i < m-1; i++) {
            for (int j = 0; j < n-1; j++) {
                if (s1[i] == s2[j]) {
                    arr[i + 1][j + 1] = arr[i][j] + 1;//相等找斜对角
                }
                else {
                    arr[i + 1][j + 1] = max(arr[i + 1][j], arr[i][j + 1]);//不相等从左/上max继承
                }
            }
        }
	  //test output
        cout << "s p ";
        for (int j = 0; j < n; j++) {
            cout << s2[j] << " ";
        }
        cout << "\np ";
        for (int j = 0; j < n; j++) {
            cout << arr[0][j] << " ";
        }
        cout << endl;
        for (int i = 1; i < m; i++) {
            cout << s1[i-1] << " ";
            for (int j = 0; j < n; j++) {
                cout << arr[i][j] << " ";
            }
            cout << endl;
        }//test
        
        stack <char>st;
        int i = m - 1, j = n - 1;
        while (i > 0&&j > 0) {
            //s1[i] != s2[j]
            if (arr[i][j] == max(arr[i - 1][j], arr[i][j - 1])) {
                if (arr[i - 1][j] > arr[i][j - 1]) {
                    i--;
                }
                else {
                    j--;
                }
            }
            //s1[i] == s2[j]
            else {
                st.push(s1[i-1]);
                //cout << s1[i-1] << "test" << endl;
                i--;
                j--;
            }
        }
        string res = "";
        //output
        while (!st.empty()) {
            char ch=st.top();
            res += ch;
            st.pop();
        }
        if (arr[m - 1][n - 1] == 0)
            return "-1";
        return res;
        for (i = 0; i < m; i++) {
            delete[]arr[i];
        }
        delete[]arr;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        int m = s1.length()+1;
        int n = s2.length()+1;
        int** arr = new int* [m];
        for (int i = 0; i < m; i++) {
            arr[i] = new int[n];
        }
        for(int i = 0; i < m; i++) {
            arr[i][0] = 0;
        }
        for (int j = 0; j < n; j++) {
            arr[0][j] = 0;
        }
        for (int i = 0; i < m-1; i++) {
            for (int j = 0; j < n-1; j++) {
                if (s1[i] == s2[j]) {
                    arr[i + 1][j + 1] = arr[i][j] + 1;//相等找斜对角
                }
                else {
                    arr[i + 1][j + 1] = max(arr[i + 1][j], arr[i][j + 1]);//不相等从左/上max继承
                }
            }
        }
        cout << "s p ";
        for (int j = 0; j < n; j++) {
            cout << s2[j] << " ";
        }
        cout << "\np ";
        for (int j = 0; j < n; j++) {
            cout << arr[0][j] << " ";
        }
        cout << endl;
        for (int i = 1; i < m; i++) {
            cout << s1[i-1] << " ";
            for (int j = 0; j < n; j++) {
                cout << arr[i][j] << " ";
            }
            cout << endl;
        }//test
        
        stack <char>st;
        int i = m - 1, j = n - 1;
        while (i > 0&&j > 0) {
            //s1[i] == s2[j]
            if(s1[i-1] == s2[j-1]) {
                st.push(s1[i-1]);
                //cout << s1[i-1] << "test" << endl;
                i--;
                j--;
            }
            //s1[i] != s2[j]
            else{
                if (arr[i - 1][j] > arr[i][j - 1]) {
                    i--;
                }
                else {
                    j--;
                }
            }
        }
        string res = "";
        //output
        while (!st.empty()) {
            char ch=st.top();
            res += ch;
            st.pop();
        }
        if (arr[m - 1][n - 1] == 0)
            return "-1";
        return res;
        for (i = 0; i < m; i++) {
            delete[]arr[i];
        }
        delete[]arr;
    }
};