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

#include <unordered_map>
#include <vector>
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
        unordered_map<char, vector<int>> hash_map;
        unordered_map<int, char> reverse_map;
        vector<int> map_arr;
        for(int i=0;i<s1.size();i++){
            vector<int> tmp;
            if(hash_map.find(s1[i])!=hash_map.end())
                tmp = hash_map[s1[i]];
            tmp.push_back(i);
            hash_map[s1[i]] = tmp;
            reverse_map[i] = s1[i];
        } 
        for(int i=0;i<s2.size();i++)
            if(hash_map.find(s2[i])!=hash_map.end()){
                vector<int> tmp = hash_map[s2[i]];
                for(int j = tmp.size()-1;j>=0;j--)
                    map_arr.push_back(tmp[j]);
            }         
        if(map_arr.size()==0)
            return "-1";
        vector<int> dp(map_arr.size()+2);
        int maxlen = 1;
        dp[1] = map_arr[0];
        vector<int> pre(map_arr.size()+2);
        fill(pre.begin(),pre.end(),-1);
        vector<int> path(map_arr.size()+2);
        path[0] = -1;
        vector<int> path_ans;
        string ans;
        for(int i = 1;i<map_arr.size();i++){
            if(map_arr[i]>dp[maxlen]){
                maxlen++;
                dp[maxlen] = map_arr[i];
                pre[i] = path[maxlen-1];
                path[maxlen] = i;
            }else{
                int pos = lower_bound(dp.begin()+1, dp.begin() + maxlen , map_arr[i], less<int>()) - dp.begin();
                dp[pos] = map_arr[i];
                pre[i] = path[pos-1];
                path[pos] = i;
            }
        }
        int i = path[maxlen];
        while(i!=-1){
            path_ans.push_back(map_arr[i]);
            i = pre[i];
        }
        for(int i=path_ans.size()-1;i>=0;i--)
            ans+=reverse_map[path_ans[i]];
        return ans;

    }
};

将s1映射为一个上升序列，该映射函数设为f,则s3 = f(s2),该问题即为求s3的最长上升子序列。求出结果为s4,则原题目结果为f^-1(s4).关键问题在于s1中要是包含重复元素怎么处理？做法是将所有出现的位置均记录在一个序列里，然后在对s2做映射时，对该元素的序列降序。例如s1：a,b,c,a,d,c ；s2: c,a,b,c,d,a；则f为

则s3 = f(s2) = 5 2 3 0 1 5 2 4 3 0

s4 = 0 1 2 4

s5 = f^-1(s4) = a b c d