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

#include<string>
#include <vector>

using namespace std;

class Solution {


  public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    int max(int a, int b) {
        return a > b ? a : b;
    }
    string LCS(string s1, string s2) {
        // write code here
        int len1, len2;
        len1 = s1.size();
        len2 = s2.size();
        vector<int>w(len2 + 1, 0);
        vector<vector<int>>arr(len1 + 1, w);

        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                } else {
                    arr[i][j] = max(arr[i][j - 1], arr[i - 1][j]);
                }
            }
        }
        int k = 0;
        int i = len1, j = len2;
        string str;

        //for (; (i > 0) && (j > 0);)
        //{
        //    if (s1[i-1] == s2[j-1])
        //    {
        //        str[k++] = s1[i-1];
        //        i--; j--;
        //    }
        //    else
        //    {
        //        if (arr[i][j] == arr[i - 1][j])
        //        {
        //            i--;
        //        }
        //        else
        //        {
        //            j--;
        //        }
        //    }
        //}
        while (i > 0 && j > 0) {
            if (s1[i - 1] == s2[j - 1]) {
                str = str + s1[i - 1];
                //str.append(1, s1[i - 1]);
                i--;
                j--;
            } else {
                if (arr[i][j] == arr[i - 1][j]) {
                    i--;
                } else {
                    j--;
                }
            }
        }
        if(str.empty()) return "-1";
        reverse(str.begin(), str.end());
        return str;
    }
};

天啊终于！！对于string的赋值不能像C一样，需要用string自己的加法、或者追加！