使用Python查詢拆分字串的有效方法的數量

假設我們有一個字串s。當我們可以將s拆分成兩個非空字串p和q，其連線等於s，並且p和q中不同字母的數量相等時，則稱該拆分是有效的拆分。我們必須找到在s中可以進行的有效拆分的數量。

因此，如果輸入類似於s = "xxzxyx"，則輸出將為2，因為有多種拆分方式，但是如果我們像("xxz","xyx")或("xxzx","yx")那樣拆分，則它們是有效的。

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

  • 結果 := 0

  • left := 用於統計專案頻率的空對映

  • right := 統計s中每個字元的頻率

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

    • left[c] := left[c] + 1

    • right[c] := right[c] - 1

    • 如果right[c]為零，則

      • 移除right[c]

    • 如果left的大小與right的大小相同，則

      • 結果 := 結果 + 1

  • 返回結果

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

示例

 線上演示

from collections import Counter
def solve(s):
   result = 0
   left, right = Counter(), Counter(s)
   for c in s:
      left[c] += 1
      right[c] -= 1
      if not right[c]:
         del right[c]
      if len(left) == len(right):
         result += 1
   return result
s = "xxzxyx"
print(solve(s))

輸入

"xxzxyx"

輸出

2

更新於：2021年5月29日

303 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始
廣告