Python程式：移除相鄰不同位後找到最短字串

假設我們有一個二進位制字串s，如果兩個相鄰字元不同，我們可以刪除它們。最終，我們需要找到如果可以執行此操作任意多次，我們可以獲得的最短字串的長度。

因此，如果輸入類似於s = "1100011"，則輸出將為1，因為刪除“10”後得到“10011”，然後再次刪除“10”，它將變為“011”，然後刪除“01”，剩下1。

為了解決這個問題，我們將遵循以下步驟：

  • stack := 新建一個列表
  • 對於s中的每個字元c，執行以下操作：
    • 如果stack為空或stack的頂部與c相同，則
      • 將c壓入stack
    • 否則，如果stack的頂部與c不同，則
      • 從stack中彈出元素
  • 返回stack中元素的個數

讓我們看看下面的實現來更好地理解：

示例

 線上演示

class Solution:
   def solve(self, s):
      stack = []
      for c in s:
         if not stack or stack[-1] == c:
            stack.append(c)
         elif stack[-1] != c:
            stack.pop()
      return len(stack)
ob = Solution() print(ob.solve("1100011"))

輸入

"1100011"

輸出

1

更新於：2020年10月5日

239 次瀏覽

開始你的職業生涯

完成課程獲得認證

開始學習
廣告