NC561 题解 | #单词消消乐#

题意分析

• 给出n个字符串，从第一个字符串开始，和下一个字符串执行消除的操作，也就是如果当前这个字符串的最后一个字符和下一个字符串的第一个字符相等，那么这两个字符就消除，一直执行这样的操作直到字符不相等或者是其中一个字符串为空，然后将这个两个字符串剩下的字符按照先后顺序拼接成一个新的字符串，继续和下一个字符串执行类似的操作。问最后得到的字符串是什么？

思路分析

• 这个题目，我们需要先知道上一个字符串的最后的那个字符是什么，然后遍历这个新的字符串依次进行比较，最后执行相应的操作，其实就是一个很简单的模拟题。

解法一 栈模拟

• 首先，我们想到先用栈来执行模拟的操作，我们先了解一下栈是什么？栈就是一个先进后出的数据结构。如下图

• 利用栈我们可以O(1)地取到我们栈顶的元素，也就是最后的那个字符了。所以，我们维护一个栈，将最新的字符串放到栈里面，然后遍历一个待合并的字符串，看是否可以执行消除的操作，循环遍历比较直到不能为止。然后将剩下的字符串都放到栈里面，继续遍历下一个字符串，如此循环。

• 代码如下

  • 过程中维护了一个栈，只需要遍历所有的字符串的字符一遍即可，所以总的时间复杂度为所有的字符串的总长度$O(\sum S_i)O(\backslash sum\{S\_i\})$
  • 过程中利用了栈来进行模拟，空间复杂度为$O(\sum S_i)O(\backslash sum\{S\_i\})$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Words string字符串vector 
     * @return string字符串
     */
    string WordsMerge(vector<string>& Words) {
        // write code here
        stack<char> st;
        for(auto x:Words){
            int len=x.size();
            int key=len;
            for(int i=0;i<len;i++){
                // 如果当前栈里面还有字符，同时和这个字符当前位置的字符相同，那么执行出栈操作
                if(!st.empty()&&st.top()==x[i]){
                    st.pop();
                }else{
                    // 一旦发现不能消了，那么直接退出
                    key=i;
                    break;
                }
            }
            // 之后的字符串就直接放到栈里面即可
            for(int i=key;i<len;i++){
                st.push(x[i]);
            }
        }
        
        string ans="";
        // 将栈里面的字符提取出来，然后进行反转
        while(!st.empty()){
            ans+=st.top();
            st.pop();
        }
        
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

解法二 双指针模拟

• 对于第二种解法，我们利用两个指针来判断，对于两个需要待执行消除的字符串A和B，我们定义j和k来维护哪个区间范围内的字符是需要保留的，这样的话对于剩下的字符我们只需要进行拼接即可。维护j和k的话就是j从字符串A的后面往前走，k从字符串B的前面往后走，直到遇到第一次字符不相等。

• 代码如下
  • 首先，利用双指针的操作，我们删除的字符只需要执行一次遍历的操作，而留下来的字符需要执行n-1次的重新拼接的操作，所以其实最坏的时间复杂度还是$O(n{\sum }_{i=1}^{n}S[i]\mathrm{.}size())O(n\backslash sum\_\{i=1\}^n\{S[i].size()\})$
  • 过程中需要用一个临时的字符串存储拼接后的字符串，空间复杂度为$O({\sum }_{i=1}^{n}s[i]\mathrm{.}size())O(\backslash sum\_\{i=1\}^n\{s[i].size()\})$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Words string字符串vector 
     * @return string字符串
     */
    string WordsMerge(vector<string>& Words) {
        // write code here
        // 获得初始的字符串
        string now=Words[0];
        int n=Words.size();
        // 循环遍历Words数组
        for(int i=1;i<n;i++){
            // 定义两个指针，j指向now的最后的位置，k指向当前的Words中字符串的第一个位置
            int j=now.size()-1,k=0;
            int len=Words[i].size();
            // 循环进行移动，直到不能消除为止
            while(j>=0&&k<len){
                if(now[j]==Words[i][k]){
                    j--,k++;
                }else{
                    break;
                }
            }
            // 将剩余的字符串拼接起来重新赋值给now，进入下一轮循环处理
            string tmp="";
            // now的前半部分
            for(int s=0;s<=j;s++){
                tmp+=now[s];
            }
            // Words[i]的后半部分
            for(;k<len;k++){
                tmp+=Words[i][k];
            }
            
            now=tmp;
        }
        
        
        return now;
    }
};