一.题目描述
NC561单词消消乐
牛妹会给牛牛n个单词，牛妹要求牛牛将这n个单词按照以下方式合并：
(1)从左往右合并单词，将合并后的单词作为第一个单词再与后面单词合并
例如有三个单词"a"，"b"，"c"，先将"ab"合并，最后将合并后的"ab"与"c"合并得到"abc"。
(2)如果最左边单词结尾字母与其后面一个的单词的开始字母相同，则最左边单词的结尾字母与之后一个单词的开始字母都会抵消掉而消失，重复上述操作直到某一个单词为空或者最左端的结尾字母与之后单词的开始字母不同，然后合并这两个单词作为一个单词放置再最左边。
例如 "aab" "bac"合并之后会得到"ac"
二.算法(模拟)
理解题目意思后，我们直接采用模拟的方法，用left和right表示前后两个字符串，初始left为第0个字符串，right为第1个字符串，然后用比较left的首和right的尾，找到第一个不同的left字符串尾和right字符串首，然后将left从头到不相同的第一位和right的不相同第一位到最后一位拼接，然后顺序进行最后返回left字符串。下面是完整代码：

class Solution {
public:
    string WordsMerge(vector<string>& Words) {
        string left;
        left=Words[0];
        for(int i=1;i<Words.size();i++){
            string right=Words[i]; 
            //比较left和right两个字符串的长度 遍历长度小的字符串
            int mi=min(left.size(),right.size());
            int ed=0;//记录有重合的长度
            for(int j=0;j<mi;j++){ 
                if(left[left.size()-j-1]!=right[j]){ 
                    //没有重合直接结束
                    ed=j;
                    break;
                } else {
                    ed++;
                }
            }
            //最后进行拼接
            left=left.substr(0,left.size()-ed)+right.substr(ed);
        }
        return left;
    }
};

时间复杂度：需要对所以的Words进行一次遍历
空间复杂度：不需要额外空间
优缺点：思路简单，代码简单便于实现。
三.算法(栈模拟)

我们使用栈这种数据结构来维护左边单词的字符，每次遇到一个字符串我们就依次比较字符串与栈顶，如果相同则弹出栈顶元素并且继续往后比较，如果找到了第一个不相同的元素，则后续元素全部入栈。最后将栈中字符全部弹出后翻转就是最后答案了。

class Solution {
public:
    string WordsMerge(vector<string>& Words) {
        stack<char> q;
        //开始的时候把第一个字符串全部入栈
        for(int i = 0; i < Words[0].size(); i++){
            q.push(Words[0][i]);
        }
        //开始依次遍历
        for(int i=1;i<Words.size();i++){
            bool ck=false; 
            //判断是否可以结束遍历
            for(int j = 0; j < Words[i].length(); j++){
                if((j==0&&q.empty())||ck){
                    ck=true;
                    q.push(Words[i][j]);
                } else{
                    if(q.top()!=Words[i][j]) {
                        //不同 开始入栈
                         q.push(Words[i][j]); 
                         ck=true;
                    } else {
                        //相同 栈顶弹出
                        q.pop();
                    }
                }
            }
        }
        string answer="";
        while(!q.empty()){
            answer+=q.top();
            q.pop();
        }
        //对字符串进行翻转
        reverse(answer.begin(),answer.end());
        return answer;
    }
};

时间复杂度：需要对所以的Words进行一次遍历
空间复杂度：需要开辟空间维护栈
优缺点：思路简单，代码简单便于实现。