leetcode1209：删除字符串中的所有相邻重复项 II

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

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

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

本题答案保证唯一。

示例 1：

输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。

示例 2：

输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释： 
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"

示例 3：

输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"

提示：

1 <= s.length <= 10^5
2 <= k <= 10^4
s 中只含有小写英文字母。

附赠 leetcode 地址：leetcode

var removeDuplicates = function(s, k) {
    let stack = [];
    for(let _s of s){
        const last = stack.pop();
        if(!last || last[0] !== _s){
            stack.push(last)
            stack.push(_s)
        }else if(last.length < k-1){
            stack.push(last + _s)
        }
    }

    return stack.join('')
};

function delStr(s = '', k = 2) {
            if (typeof s !== 'string' || k < 2) {
                return;
            }
            let c = new RegExp(`(.)\\1{${k-1}}`, 'g');
            while (s !== s.replace(c, '')) {
                s = s.replace(c, '');
            }

            return s;
     }

原理跟昨天的题是一样的，不过昨天的题是一次入栈一个，今天是k个。那我们就让它每次入栈 k-1 个，站头的 k-1 个元素的第一个如果与当前准备入栈的元素相同，则代表k个元素是一样的，则无需入栈。

var removeDuplicates = function(s, k) {
    let stack = [];
    for(let c of s){
        const prev = stack.pop();
        if(!prev || prev[0] !== c){
            stack.push(prev)
            stack.push(c)
        }else if(prev.length < k-1){
            stack.push(prev + c)
        }
    }
    return stack.join('')
};

解答：利用栈

解题思想： 遍历字符串依次入栈，入栈时，判断当前元素与栈头元素是否一致，如果不一致则入栈，如果一致，判断栈头字符是否长度为 k - 1 ，如果为 k-1 ，即加入该字符时，满足连续相同字符 k 个，此时，需要栈头出栈，当前字符不进栈，如果小于 k-1 ，则取出栈头字符，加上当前字符，重新入栈

代码实现：

const removeDuplicates = function(s, k) {
    let stack = []
    for(let c of s) {
        let prev = stack.pop()
        if(!prev || prev[0] !== c) {
            stack.push(prev)
            stack.push(c)
        } else if(prev.length < k-1) {
            stack.push(prev+c)
        }
    }
    return stack.join('')
};

时间复杂度：O(n)

空间复杂度：O(n)

leetcode

暴力来一波

var removeDuplicates = function(s, k) {
    function findRepeatPos (s, k) {
        for (let i = 0; i < s.length - k + 1; i++) {
            let flag = true
            for (let j = i; j < i + k - 1; j++) {
                if (s[j] !== s[j + 1]) {
                    flag = false
                    break
                }
            }
            if (flag === true) {
                return [i, i + k - 1]
            }
        }
        return [-1]
    }

    while (true) {
        let [start, end] = findRepeatPos(s, k)
        console.log(start, end)
        if (start === -1) {
            return s
        } else {
            s = s.slice(0, start) + s.slice(end + 1)
        }
    }
    return s
};

function delStr(s = '', k = 2) {
            if (typeof s !== 'string' || k < 2) {
                return;
            }
            let c = new RegExp(`(.)\\1{${k-1}}`, 'g');
            while (s !== s.replace(c, '')) {
                s = s.replace(c, '');
            }

            return s;
     }

这种做法可以，但是它采用循环匹配替换，花费时间较长，需要考虑一下时间复杂度问题

采用两个栈来进行:
function removeDuplicateK(s, k) {
    if(k <= 0) {
        return s;
    }   
    let stack1 = new Stack();
    for(let i=0; i<s.length; i++) {
        let iValue = s[i]
            stack2 = new Stack(),
            j = 0,
            isValid = true;
        while(j < k-1) {
            let popValue = stack1.pop();
            if(popValue !== null){
                stack2.push(popValue);
            }
            if(popValue === null || popValue !== iValue) {
                isValid = false;
                break;
            }
            j += 1;
        }
        if(!isValid) {
            while(stack2.length > 0) {
                stack1.push(stack2.pop());
            }
            stack1.push(iValue);
        }
    }
    return stack1.dataStore.join('');
}

正则 + 递归

var removeDuplicates = function(s, k) {
  if (s.length < k) {
    return s
  }

  const repeatLenStrRe = new RegExp(`(.)\\1{${ k - 1 }}`, 'g')
  const replaceStr = s.replace(repeatLenStrRe, '')
  // 说明没有需要再匹配的了
  if (replaceStr === s) {
    return replaceStr
  } else {
    return removeDuplicates(replaceStr, k)
  }
};

大家来评评理。对于以下测试用例，我输出“is”有什么不对吗

"pbbcggttciiippooaais"
2

预期结果
"ps"

下面是我的代码

var removeDuplicates = function(s, k) {
  for (let left = 0; i < s.length - k + 1; left++) {
    let right = i;
    while (s[right + 1] == s[left]) {
      right = right + 1;
    }

    const gap = right - left + 1;
    if (gap >= k) {
      s = s.substr(0, i) + s.substr(i + gap, s.length)
      left = -1
    }
  }
  return s
};

执行过程输出

pbbcggttciiippooaais -->  pcggttciiippooaais
pcggttciiippooaais -->  pcttciiippooaais
pcttciiippooaais -->  pcciiippooaais
pcciiippooaais -->  piiippooaais
piiippooaais -->  pppooaais
pppooaais -->  ooaais
ooaais -->  aais
aais -->  is

和删除相邻重复项是同一个类型，利用栈来存储扫描过的字符，不一样的是该题支持 k 个，这个理论上可以按照上一题一样的原则，直接推栈就好了，但是出栈的时候，考虑到假如 k 值很大，会做很多重复性的 pop 工作，所以我这里将栈的节点从单纯存储读取的字符，改为一个对象，对象保存了读取的字符，和已经读取的字符数量，这样每次 pop 只需要一次即可完成任务

interface StackNode {
    value: string;
    count: number;
}
const removeDuplicates = (source: string, k: number) => {
    if (source.length <= 0 || k <= 0 || source.length < k) return source;
    const stack: StackNode[] = [];
    for (let i = 0; i < source.length; i++) {
        const char = source[i];
        if (stack.length <= 0) {
            stack.push({ value: char, count: 1 });
            continue;
        }
        const lastStackNode = stack[stack.length - 1];
        if (lastStackNode.value !== source[i]) {
            stack.push({ value: char, count: 1 });
            continue;
        }
        if (lastStackNode.count === (k - 1)) {
            stack.pop();
        } else {
            lastStackNode.count++;
        }
    }
    return stack.reduce((prev, cur) => prev + cur.value.repeat(cur.count), '');
};

Navigation Menu

Repository navigation

leetcode1209：删除字符串中的所有相邻重复项 II #27

解答：利用栈

正则 + 递归

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

leetcode1209：删除字符串中的所有相邻重复项 II #27

Description

Activity

7777sea commented on Apr 27, 2020

huangd-d commented on Apr 27, 2020

AiKunnnnn commented on Apr 27, 2020

sisterAn commented on Apr 27, 2020

解答：利用栈

twinkle77 commented on Apr 28, 2020

sisterAn commented on Apr 28, 2020

zhaojinzhao commented on May 7, 2020

HanTianPeng commented on May 10, 2020

qianlongo commented on Aug 22, 2020

正则 + 递归

Forever17s commented on Feb 27, 2021

JohnApache commented on Apr 29, 2021

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions