基于 leetcode 的算法学习记录文章，使用语言主要是 JavaScript，可能会有少于 C/Python 实现，在没标明的情况下默认都是 JavaScript 实现。

约定 ：
1. 有每日 角标的标识是每日一题的题目
2. 有leetcode角标的标识是该方案是Leetcode 网站上的题解

删除字符串中重复的字符

https://leetcode.com/articles/remove-all-adjacent-duplicates-in-string/

题解：删除靠着的重复字符，然后对删除后的字符执行同样的操作，直到没有紧靠着的重复字符为止。

比如： abbaca => del, bb => aaca => del, aa => ca

最终 abbaca 经过处理得到 ca 。

while 循环版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

  const del = str => str.replace(/([a-z])\1{1,}/gi, '');

  function rmDupsWithWhile(current) {
    let last = ''
    while (last !== current) {
      last = current
      current = del(current)
    }

    return current
  }


  console.time('Time')
  console.log('result:', rmDupsWithWhile('abbaca'))
  console.timeEnd('Time')

result: ca
Time: 7.468ms
undefined

原理含简单，就是不断的使用正则去重复替换掉重复的连续字符，直到最后 last === current 为止，

因为一旦没有重复连续字符了， replace 的结果都最终一样。

正则递归版本(尾调用未优化)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

  const str = 'abbaca'

  const del = s => s.replace(/([a-z])\1{1,}/gi, '')

  function rmDupsWithRecursionNoOptimized(current, last) {

    if (last == current) return current

    last = current
    current = del(current)

    const res = rmDupsWithRecursionNoOptimized(current, last)
    // 不满足尾调用优化：未立即返回执行结果，非最后一个语句
    return res
  }

  console.time('Time')
  const res = rmDupsWithRecursionNoOptimized(str)
  console.timeEnd('Time')
  console.log(res)

Time: 0.336ms
ca
undefined

正则递归版本(尾调用优化)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

  const str = 'abbaca'

  const del = s => s.replace(/([a-z])\1{1,}/gi, '')

  function rmDupsWithRecursionOptimized(current, last) {

    if (last == current) return current

    last = current
    current = del(current)

    // 尾调用优化条件： 1. 立即返回结果，2. 无变量引用，3. 最后一行
    return rmDupsWithRecursionOptimized(current, last)
  }

  console.time('Time')
  const res = rmDupsWithRecursionOptimized(str)
  console.timeEnd('Time')
  console.log(res)

Time: 0.604ms
ca
undefined