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

题目

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

题解

模拟

/**
 * @param {string} S
 * @return {string}
 */
var removeDuplicates = function(S) {
  let sa = S.split("");
  let i = 0;
  while (i < sa.length - 1 && i >= 0) {
    if (sa[i] == sa[i + 1]) {
      sa.splice(i, 2);
      if (i != 0) i--;
    } else {
      i++;
    }
  }
  return sa.join("");
};

替换

只有 26 种情况，用 replace 把相同的情况替换成 ''

/**
 * @param {string} S
 * @return {string}
 */
var removeDuplicates = function(S) {
  // 初始化替换列表
  const reg = [];
  for (let i = 0; i < 26; ++i) {
    reg.push(String.fromCharCode(97 + i) + String.fromCharCode(97 + i));
  }

  // 替换后如果长度变化了就继续
  let l;
  do {
    l = S.length;
    for (let r of reg) {
      S = S.replace(r, "");
    }
  } while (l != S.length);
  return S;
};

栈

利用栈的特性，不断进栈如果是相同的就出栈

/**
 * @param {string} S
 * @return {string}
 */
var removeDuplicates = function(S) {
  let stack = [];
  for (let s of S) {
    // 如果栈不空，栈顶元素等于下一个元素就出栈
    if (stack.length) {
      let top = stack[stack.length - 1];
      if (s === top) {
        stack.pop();
        continue;
      }
    }
    stack.push(s);
  }
  return stack.join("");
};