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

题目

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：

  1. 输入："abbaca"
  2. 输出："ca"
  3. 解释：
  4. 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。
  5. 之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

  1. 1 <= S.length <= 20000
  2. S 仅由小写英文字母组成。

题解

首先是最暴力的方法，直接模拟：

  1. class Solution(object):
  2.     def removeDuplicates(self, S):
  3.         i = 0
  4.         while i < len(S)-1:
  5.             if S[i] == S[i+1]:
  6.                 S = S[:i]+S[i+2:]
  7.                 i = max(0, i-1)
  8.             else:
  9.                 i += 1
  10.         return S

该程序排名 25%， 因为里面有很多字符串的合并操作，这是非常消耗时间的。
所以我们考虑用链表来模拟，如果 S[i] == S[Next[i]]，那么立刻将 i 的前一个元素指向 i 的后两个元素 Next[last_i] = Next[Next[i]]。
为了减少边界情况的考虑，我们可以加一个哨兵节点：S='0'+S ，这样 S[0] 就成为了永远存在的表头。

  1. class Solution(object):
  2.     def removeDuplicates(self, S):
  3.         i = 0
  4.         S = '0'+S
  5.         Next = list(range(1, len(S)+1))
  6.         Next[-1] = -1
  7.         Last = []
  8.         while Next[i] >= 0:
  9.             if S[i] == S[Next[i]]:
  10.                 last_i = Last.pop()
  11.                 Next[last_i] = Next[Next[i]]
  12.                 i = last_i
  13.             else:
  14.                 Last.append(i)
  15.                 i = Next[i]
  16.         i = 0
  17.         L = []
  18.         while i >= 0:
  19.             L.append(S[i])
  20.             i = Next[i]
  21.         return ''.join(L[1:])

执行用时：92 ms, 在所有 Python 提交中击败了32.92%的用户 内存消耗：14.4 MB, 在所有 Python 提交中击败了5.40%的用户

但是结果居然排在 33%，这不是简单题么？
瞟了一眼题解，瞬间恍然大悟，是自己想复杂了，直接用栈就OK了

  1. class Solution(object):
  2.     def removeDuplicates(self, S):
  3.         L = []
  4.         for s in S:
  5.             if L and L[-1] == s:
  6.                 L.pop()
  7.             else:
  8.                 L.append(s)
  9.         return ''.join(L)