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

在这篇博客中，我们将探讨如何使用JavaScript来删除字符串中的所有相邻重复项。我们将从分析问题开始，逐步讲解代码实现，并在最后进行总结。

分析

问题的要求是删除字符串中的所有相邻重复项。例如，给定字符串 "abbaca"，结果应该是 "ca"，因为：

• "abbaca" -> 删除 "bb" -> "aaca"
• "aaca" -> 删除 "aa" -> "ca"

为了实现这个功能，我们可以使用一个栈（stack）来逐一处理字符串中的字符。如果当前字符与栈顶的字符相同，则将栈顶字符弹出，否则将当前字符推入栈中。这样一遍遍历字符串，我们就能删除所有相邻重复项。

代码

下面是实现这一功能的JavaScript代码：

/**
 * @param {string} s
 * @return {string}
 */
const removeDuplicates = function (s) {
  // 遍历字符串，把字符串push到stack里面，如果当前加入的字符和末尾的字符相同就pop掉
  const len = s.length;
  const result = [];
  for (let i = 0; i < len; i++) {
    if (result.slice(-1)[0] === s.charAt(i)) {
      result.pop();
    } else {
      result.push(s.charAt(i));
    }
  }
  return result.join('');
};

代码详解

1.初始化

const len = s.length;
const result = [];

2.遍历字符串

for (let i = 0; i < len; i++) {
  if (result.slice(-1)[0] === s.charAt(i)) {
    result.pop();
  } else {
    result.push(s.charAt(i));
  }
}

使用一个 for 循环来遍历字符串中的每一个字符：

• result.slice(-1)[0]：获取栈顶的字符（即 result 数组的最后一个元素）。
• s.charAt(i)：获取当前遍历到的字符。
• 如果当前字符与栈顶字符相同，则弹出栈顶字符（表示移除相邻重复项）。
• 否则，将当前字符推入栈中。

3.返回结果

return result.join('');

总结

通过使用栈，我们能够高效地解决删除字符串中所有相邻重复项的问题。这个方法的时间复杂度为 O(n)，其中 n 是字符串的长度，因为我们只需遍历字符串一次。

在代码实现中，我们利用了栈的后进先出（LIFO）特性来追踪相邻字符，当遇到重复字符时就将其弹出，最终得到一个没有相邻重复项的字符串。

这种方法不仅简单直观，而且效率也很高，适合在需要处理相邻重复项问题的场景中使用。希望这篇博客对你理解和实现这一功能有所帮助！