Python程式：將兩個字串分割成每個分割槽都形成異位詞

假設我們有兩個非空字串 s 和 t，它們長度相同。我們需要將它們分割成子字串，使得 s 和 t 的每個子字串對具有相同的大小，並且它們互為異位詞。現在找到切割索引，使其導致 s 和 t 的最大切割數。如果找不到結果，則返回空列表。

因此，如果輸入類似於 s = "bowcattiger" t = "owbactietgr"，則輸出將為 [0, 3, 5, 6, 10]，因為我們可以將字串分割成 5 個分割槽，使得每個字串互為異位詞。s = ["bow", "ca", "t", "tige", "r"]，t = ["owb", "ac", "t", "ietg", "r"]

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

  • intervals := 一個新的列表
  • cs := 一個對映，包含 s 中存在的字元及其頻率
  • ct := 一個對映，包含 t 中存在的字元及其頻率
  • 如果 cs 與 ct 不相同，則
    • 返回一個新的列表
  • 對於 x 從 s 的大小 - 1 到 0，執行以下操作：
    • cs[s[x]] := cs[s[x]] - 1
    • ct[t[x]] := ct[t[x]] - 1
    • 如果 cs 與 ct 相同，則
      • 將 x 插入到 intervals 的末尾
  • 對列表 intervals 進行排序並返回

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

示例

 即時演示

from collections import Counter
class Solution:
   def solve(self, a, b):
      intervals = []
      ca = Counter(a)
      cb = Counter(b)
      if ca != cb:
         return []
      for x in reversed(range(len(a))):
            ca[a[x]] -= 1
            cb[b[x]] -= 1
            if ca == cb:
               intervals.append(x)
      return sorted(intervals)
ob = Solution()
s = "bowcattiger"
t = "owbactietgr"
print(ob.solve(s, t))

輸入

"bowcattiger", "owbactietgr"

輸出

[0, 3, 5, 6, 10]

更新於: 2020年10月5日

432 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告