LeetCode之最长公共子序列问题LCS解决方法_leetcode lcs

Leetcode官网解答 使用动态规划原理，请参考原文地址：

https://leetcode-cn.com/problems/longest-common-subsequence/solution/zui-chang-gong-gong-zi-xu-lie-by-leetcod-y7u0/

图片来源官网解答：

那么问题来了，如何实现输出答案字符串呢？

下面是我的思路;

使用queue用来存储中间数据（字符串及下一次的ID），相当于BFS遍历。

从最后一个网格倒叙进行解答，查询字符是否一致，一致则加入字符串否则存储下一个的可能方向。

直到达到最底层。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> vec(m+1,vector<int>(n+1));
        
        for(int i = 1; i <= m; i++)
        {
            char c1 = text1[i-1];
            for(int j = 1; j <= n; j++)
            {
                char c2 = text2[j-1];
                if(c1 == c2)
                    vec[i][j] = vec[i-1][j-1]+1;
                else
                    vec[i][j] = max(vec[i-1][j],vec[i][j-1]);
            }
        }
 
        //print all subsequences
        //last char position
        queue<pair<string,vector<int>>> q;
        q.push(pair<string,vector<int>>("",{m,n}));
        while(!q.empty())
        {
            string curr = q.front().first;
            vector<int> pos = q.front().second;
            q.pop();
            if(text1[pos[0]-1] == text2[pos[1]-1])
            {
                curr = text1[pos[0]-1] + curr;
                if(pos[0] > 1 && pos[1] > 1)
                {
                    q.push(pair<string,vector<int>>(curr,{pos[0]-1,pos[1]-1}));
                }
            }
            else
            {
                if(vec[pos[0]-1][pos[1]] == vec[pos[0]][pos[1]])
                {
                    if(pos[0] > 1 && pos[1] >= 1)
                    {
                        q.push(pair<string,vector<int>>(curr,{pos[0]-1,pos[1]}));
                    }
                }
                if(vec[pos[0]][pos[1]-1] == vec[pos[0]][pos[1]])
                {
                    if(pos[0] >= 1 && pos[1] > 1)
                    {
                        q.push(pair<string,vector<int>>(curr,{pos[0],pos[1]-1}));
                    }
                }
            }
           if(curr.length() == vec[m][n])
            cout << curr << endl;
 
        }
        return vec[m][n];
 
    }
    
};