Python程式：查詢使括號有效所需的最少刪除次數

假設我們有一個包含括號 '('、')' 和小寫英文字母的字串 s。我們必須刪除最小數量的括號（'(' 或 ')'，從任何位置）以便生成的括號字串有效，並最終返回任何有效的字串。這裡的括號字串在滿足所有這些條件時才是有效的：

  • 字串為空且僅包含小寫字元，或者

  • 字串可以寫成 AB（A 與 B 連線）的形式，其中 A 和 B 是有效的字串，或者

  • 字串可以寫成 (A) 的形式，其中 A 是一個有效的字串。

因此，如果輸入類似於 s = "m)n(o)p"，則輸出將是 "mn(o)p"

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

  • stack := 新建一個列表

  • indexes := 新建一個集合

  • i := 0

  • 對於s中的每個字元c，執行：

    • 如果c 等於 '('，則

      • 將i壓入棧中

    • 否則，如果c 等於 ')'，則

      • 如果棧的大小等於 0，則

        • 將i插入到indexes中

      • 否則，

        • 從棧中彈出

      • i := i + 1

  • ret := 空字串

  • indexes := 將所有元素儲存到indexes中

  • 對於從0到s的大小-1的範圍內的每個i，執行：

    • 如果i不在indexes中，則

      • ret := ret + s[i]

  • 返回ret

示例

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

def solve(s):
   stack = []
   indexes = set()
   i = 0

   for c in s:
      if c == '(':
         stack.append(i)
      elif c == ')':
         if len(stack) == 0:
            indexes.add(i)
         else:
            stack.pop()
      i += 1

   ret = ''
   indexes = indexes.union(stack)
   for i in range(len(s)):
      if i not in indexes:
         ret += s[i]

   return ret

s = "m)n(o)p"
print(solve(s))

輸入

"m)n(o)p"

輸出

mn(o)p

更新於：2021年10月7日

瀏覽量：297

啟動您的職業生涯

透過完成課程獲得認證

開始
廣告