题解 | #单词消消乐#

题意思路：
将这n个单词按照以下方式合并：

1.从左往右合并单词，将合并后的单词作为第一个单词再与后面单词合并

2.如果最左边单词结尾字母与其后面一个的单词的开始字母相同，则最左边单词的结尾字母与之后一个单词的开始字母都会抵消掉而消失，重复上述操作直到某一个单词为空或者最左端的结尾字母与之后单词的开始字母不同。
例如 与合并之后会得到
方法一：双指针模拟
指针从第一个单词的右边结尾字母开始，

指针从第二个单词的左边开始字母开始

如果相同则，

直到i与j指向的字符不同则合并第一个字母从开头到i的部分和第二个字母从j到结尾的部分

复杂度分析

时间复杂度：O()，为字符的长度；

空间复杂度：O()，不需要额外空间存储.

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Words string字符串vector 
     * @return string字符串
     */
    string WordsMerge(vector<string>& Words) {
        // write code here
        string ans;
        for(int i=0;i<Words.size();i++){
            if(!ans.size())ans+=Words[i];//如果当前为空加入字符串
            else {
                int len=ans.size(),j=0;//定义双指针
                len--;
                while(len>=0&&j<Words[i].size()&&ans[len]==Words[i][j]){
                    len--,j++;//指针len从第一个单词的右边结尾字母开始，指针j从第二个单词的左边开始字母开始n如果相同则len--，j++
                }
                ans=ans.substr(0,len+1)+Words[i].substr(j);//最后ans更新为两个字符串不同的部分

            }
        }
        return ans;
    }
};

方法二：栈模拟

通过栈对先进后出的字符不断取出与第二个字符串从左到右一一进行比较，

相同字符则弹出栈顶，否则将第二个字符串剩下不同的字符加入栈中

最后取出栈内字符翻转输出

复杂度分析

时间复杂度：O()，为字符的长度；

空间复杂度：O()，栈进行模拟存储

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Words string字符串vector 
     * @return string字符串
     */
    string WordsMerge(vector<string>& Words) {
        // write code here
        string ans;
        stack<char>st;
        for(int i=0;i<Words[0].size();i++)st.push(Words[0][i]);//加入栈中
        for(int i=1;i<Words.size();i++){
            int j=0,len=Words[i].size();
            while(st.size()&&j<len){//对栈中的字符不断取出与第二个字符串从左到右一一进行比较，
                if(st.top()==Words[i][j]){//相同字符则弹出栈顶，
                    st.pop();j++;
                }
                else break;
            }
            while(j<len){//否则将第二个字符串剩下不同的字符加入栈中
                st.push(Words[i][j]);
                j++;
            }
        }
        while(st.size()){//取出栈顶
            ans+=st.top();
            st.pop();
        }
        reverse(ans.begin(), ans.end());//翻转字符串
        return ans;
    }
};