Python 中移除字符串中所有相邻重复字符

假设我们有一个由小写字母组成的字符串 S；将执行重复字符移除操作。这将通过选择两个相邻且相等的字母并将其移除来完成。

我们将重复从 S 中移除重复字符，直到没有剩余的重复字符。

在所有此类重复字符移除完成后返回字符串。保证答案是唯一的。

假设字符串是“abbacaca”，则答案将是“caca”。首先删除重复字符 bb，然后字符串变为“aacaca”，然后移除 aa，然后字符串变为“caca”，然后没有这样的重复字符了。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个数组 st，并初始化 i := 0
  • 当 i < 字符串长度时：
    • 如果 st 包含一些元素，并且 st 的最后一个元素 = st[i]，则将 i 加 1，并从 st 中删除最后一个元素
    • 否则将 string[i] 添加到 st 中，将 i 加 1
  • 最后将 st 中的所有元素连接成一个字符串并返回

示例

让我们看看下面的实现以获得更好的理解：

 在线演示

class Solution(object):
   def removeDuplicates(self, S):
      st = []
      i = 0
      while i < len(S):
         if len(st)!=0 and st[-1]==S[i]:
            i+=1
            st.pop(-1)
         else:
            st.append(S[i])
            i+=1
      return "".join(i for i in st)
ob1 = Solution()
print(ob1.removeDuplicates("abbacaca"))

输入

"abbacaca"

输出

"caca"

更新于: 2020-04-28

3K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告