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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告