leetcode 1209

2021-03-26 阅读量

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string-ii

可以采用数组模拟链表的方法来实现。每个元素最多只会被遍历一次删除一次，复杂度为O(n)。

class Solution {
public:
    int a[100007];// 记录当前字符重复出现的次数
    int l[100007];// 记录当前元素的左边的元素编号
    int r[100007];// 记录当前元素的右边的元素编号
    string removeDuplicates(string s, int k) {
        int pos = 0;
        int len = s.length();
        // cout << len << endl;
        s = 'A' + s;
        for(int i = 0; i<=len; i++){
            l[i] = i - 1;
            r[i] = i + 1;
        }
        for(int i = 1; i<=len; i++){
            // cout << i << " " << s[i] << " " << l[i] << " " << r[i] << " " << a[l[i]] << endl;
            if(s[i]==s[l[i]]){
                // cout << "yes" << endl;
                a[i] = a[l[i]] + 1;
                // cout << a[i] << endl;
                if(a[i]==k){
                    int tmp = i;
                    int j = 0;
                  	// 递归消除
                    while(j<k){
                        tmp = l[tmp];
                        j += 1;
                    }
                    r[tmp] = i+1;
                    l[i+1] = tmp;
                }
            }
            else{
                a[i] = 1;
            }
        }

        string ans = "";
        int x = 0;
        while(r[x]<=len){
            ans += s[r[x]];
            //putchar(s[r[x]]);
            x = r[x];
        }
        //puts(""); 
        return ans;       
    }
};