单词消消乐题解

按照题意模拟即可，通过观察我们会发现第一个单词永远是从后往前抵消，而第二个单词永远是从前往后抵消，所以我们用栈保存第一个单词，用队列保存第二个单词，抵消模拟即可。时间复杂度，空间复杂度

class Solution {
public:
    /**
     * 
     * @param Words string字符串vector 
     * @return string字符串
     */
    string WordsMerge(vector<string>& Words) {
        // write code here
        int n=Words.size();
        stack<char>stk;
        queue<char>q;
        for(int i=0;i<Words[0].length();i++) stk.push(Words[0][i]);
        for(int i=1;i<n;i++) {
            while(!q.empty()) q.pop();
            for(int j=0;j<Words[i].length();j++) q.push(Words[i][j]);
            while(!q.empty()&&!stk.empty()&&q.front()==stk.top()) {
                q.pop();
                stk.pop();
            }
            while(!q.empty()) {
                stk.push(q.front());
                q.pop();
            }
        }
        string ans="";
        while(!stk.empty()) {
            ans+=stk.top();
            stk.pop();
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

由于只要在尾部插入和删除较多的情况，并且vector和string等的线性容器本身就是栈，将答案字符串ret当做栈，设置一个指针ptr指向正在访问的字符串的str头部
如果ret.back()==ret[ptr]，ret进行pop_back操作，ptr后移；否则退出比较，返回
ret+str.substr(i)即可。

class Solution {
public:
    /**
     *
     * @param Words string字符串vector
     * @return string字符串
     */
    string WordsMerge(vector<string>& Words) {
        // write code here
        string ret;
        for (int i = 0, j = 0; i < Words.size(); i++)
        {
            for (j = 0; ret.size() && Words[i].size() && Words[i][j] == ret.back(); j++,ret.pop_back());
            ret += Words[i].substr(j);
        }
        return ret;
    }
};