Python程序：移除字符串中连续重复字符后的字符串

假设我们有一个字符串 s，我们重复删除第一个连续的重复字符。我们需要找到最终的字符串。

所以，如果输入类似 s = "xyyyxxz"，那么输出将是 "z"，因为 "yyy" 是第一个连续重复的字符，会被删除。所以我们得到 "xxxz"。然后 "xxx" 将被删除，最终得到 "z"。

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

  • stack := 新建一个栈
  • i := 0
  • 当 i < s 的大小 时，执行以下操作：
    • 如果 stack 不为空，且栈顶元素与 s[i] 相同，则：
      • x := 删除栈中的最后一个元素
      • 当 i < s 的大小 且 x 与 s[i] 相同 时，执行以下操作：
        • i := i + 1
      • i := i - 1
    • 否则：
      • 将 s[i] 入栈
    • i := i + 1
  • 返回栈中元素连接后的结果

让我们看看下面的实现，以便更好地理解：

示例

 在线演示

class Solution:
   def solve(self, s):
      stack = []
      i = 0
      while i < len(s):
         if len(stack) and stack[-1] == s[i]:
            x = stack.pop()
            while i < len(s) and x == s[i]:
               i += 1
            i -= 1
            else:
               stack.append(s[i])
            i += 1
      return "".join(stack)
ob = Solution()
s = "xyyyxxz"
print(ob.solve(s))

输入

"xyyyxxz"

输出

z

更新于: 2020年10月20日

347 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告