面试真题：删除字符串中出现次数 >= 2 次的相邻字符

输入："abbbaca"
输出："ca"
解释："abbbaca" => "aaca"=>"ca"

时间复杂度: O(n), n 为字符的个数
空间复杂度: O(n), 栈所用的空间

/**
 * 删除字符串中出现次数 >= 2 次的相邻字符
 * @param {string}s
 */
function removeDuplicate(s) {
  const stack = [] // Space: O(n)
  let top
  let next
  let i = 0
  while (i < s.length) { // Time: O(n)
    top = stack[stack.length - 1]
    next = s[i]
    if (next === top) {
      // 字符串中出现了相邻字符
      // 1. 移除栈顶字符
      // 2. 移动指针, 指向下一个不同的字符
      stack.pop()
      while (s[i] === top) i += 1
    } else {
      stack.push(next)
      i += 1
    }
  }

  return stack.join('')  // Time: O(n)
}

在昨天瓶子酱的基础上增加了判断，如果下一个还是相同字符串，继续累加
没有测试用例，有问题欢迎指出

var removeDuplicates = function(s, k) {
  let stock = []
  for (let i = 0; i < s.length; i++) {
    let prev = stock.pop()
      if (!prev || prev[0] !== s[i]) { // 取第一个字符比较
        stock.push(prev)
        stock.push(s[i])
      } else if(prev.length < k - 1 || prev[0] === s[i+1]) { // 如果长度达不到删除数量 或者与下一个字符相同则继续累加
          stock.push(prev+s[i]) // 相同字符拼接在一起
      }
  }
  return stock.join('')
};

时间复杂度: O(n), n 为字符的个数
空间复杂度: O(n), 栈所用的空间

/**
 * 删除字符串中出现次数 >= 2 次的相邻字符
 * @param {string}s
 */
function removeDuplicate(s) {
  const stack = [] // Space: O(n)
  let top
  let next
  let i = 0
  while (i < s.length) { // Time: O(n)
    top = stack[stack.length - 1]
    next = s[i]
    if (next === top) {
      // 字符串中出现了相邻字符
      // 1. 移除栈顶字符
      // 2. 移动指针, 指向下一个不同的字符
      stack.pop()
      while (s[i] === top) i += 1
    } else {
      stack.push(next)
      i += 1
    }
  }

  return stack.join('')  // Time: O(n)
}

👍👍👍

解题思路：保证相同字符串始终作为栈的一个元素进行存储。
时间复杂度:O(n), 空间复杂度O(n)

function removeDuplicateMoreTwo(s) {
    let stack1 = new Stack();
    for(let i=0; i<s.length; i++) {
        let popValue = stack1.pop(),
            iValue = s[i];
        
        if(popValue === null) {
            stack1.push(iValue);
        }else if(popValue[0] !== iValue) {
            if(popValue.length >= 2) {
                let secondPopValue = stack1.pop();
                if(secondPopValue === iValue){
                    stack1.push(secondPopValue + iValue);
                }else{
                    stack1.push(secondPopValue);
                    stack1.push(iValue);
                }
            }else{
                stack1.push(popValue);
                stack1.push(iValue);
            }
        }else if(popValue[0] === iValue) {
            stack1.push(popValue + iValue);
        }
    }
    return stack1.dataStore.join('');
}

const removeDuplicates = (str) => {
  if (str.length === 0) return ''
  let newStr = str.slice(0)
  for(let i = 0; i < newStr.length; i++) {
    if(newStr[i] === newStr[i + 1]) {
      newStr = newStr.replace(/(\w)\1+/g, '')
      i === 0 ? (i = i - 1) : (i = i - 2)
    }
  }
  return newStr
}

这个和letcode 1209有什么区别吗，从瓶子给的示例看，这完全一样啊

@supershutong

这个和letcode 1209有什么区别吗，从瓶子给的示例看，这完全一样啊

@supershutong

可以比较下输入字符串为 "aaa" 时的结果，本题返回 "" ，之前的那题返回 "a"

正则 + 递归

var removeDuplicates = function(s, k = 2) {
  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)
  }
};

const removeDup = (s) => {

let stack = []

for (let i = 0; i < s.length; i++) {
  let prev = stack.pop()
  if (prev !== s[i]) { 
    stack.push(prev)
    stack.push(s[i])
  } else if (prev === s[i + 1]) {
    stack.push(s[i + 1])
  }
}
return stack.join('')

}
removeDup('abbbaca')

function ans(str) {
// 正则+递归
const reg = /(\w)\1+/g
if(!reg.test(str)) return str
return ans(str.replace(reg, ''))
}

和删除 k 位数一样的方案, 使用带有 count 字段的对象作为栈节点, 方便 pop的操作，但是不同的是边界条件的判断，因为是，不知道会重复多少次，所以删除节点放到 push 下一个不同字符的节点前, 一起删除，

还有需要注意的边界条件有两点

删除节点后下一个值可能会和上一个值重复，这里需要再做一次单独判断，给重复的节点 count 累加，用于下轮判断的时候删除
当字符扫描到最后一位的时候，由于我们是在 push 前 pop, 做了前面的一点的判断只会给节点的 count 累加值，因为没有下一轮循环了，所以需要在这个特殊的位置，做一次单独的 pop

interface StackNode {
    value: string;
    count: number;
}
const removeDuplicates = (source: string) => {
    if (source.length <= 1) 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;
        }
        let lastStackNode = stack[stack.length - 1];
        if (lastStackNode.value !== source[i]) {
            // 先判断栈顶节点是否超过2个了，超过就删除
            // 删除节点放在这里是因为我们不知道会有多少个重复字符，可以等到字符变了的时候，再判断，这时候可以一起删除，减少pop次数
            if (lastStackNode.count >= 2) {
                stack.pop();
                lastStackNode = stack[stack.length - 1];
            }
            if (lastStackNode && lastStackNode.value === source[i]) {
                if (i === source.length - 1) {
                    // 最后一位的时候直接pop ,
                    stack.pop();
                } else {
                    lastStackNode.count++;
                }
                continue;
            }

            stack.push({ value: char, count: 1 });
            continue;
        }
        lastStackNode.count++;
    }
    return stack.reduce((prev, cur) => prev + cur.value.repeat(cur.count), '');
};

Navigation Menu

Repository navigation

面试真题：删除字符串中出现次数 >= 2 次的相邻字符 #28

正则 + 递归

const removeDup = (s) => {

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

面试真题：删除字符串中出现次数 >= 2 次的相邻字符 #28

Description

Activity

thxiami commented on Apr 28, 2020

13001920223 commented on Apr 28, 2020

sisterAn commented on Apr 28, 2020

zhaojinzhao commented on May 7, 2020

HanTianPeng commented on May 10, 2020

iconWave commented on May 29, 2020

supershutong commented on Jul 3, 2020

haydenull commented on Jul 8, 2020

qianlongo commented on Aug 22, 2020

正则 + 递归

XW666 commented on Apr 22, 2021

const removeDup = (s) => {

tomorrowIsNewDay commented on Apr 28, 2021

JohnApache commented on Apr 29, 2021

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions