Python程式：檢查字串是否可以透過子串排序操作進行轉換

假設我們有兩個數字字串s和t，我們希望使用以下操作任意多次將字串s轉換為t：1. 選擇s中的一個非空子串，並對其進行就地排序，使字元按升序排列。我們必須檢查是否可以將字串s轉換為t。

因此，如果輸入類似於s = "95643" t = "45963"，則輸出為True，因為我們可以透過例如"95643" -> "95463" -> "45963" 將s轉換為t。

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

  • places := 一個對映，其預設值型別為列表

  • 對於範圍從s的大小到0的i，執行：

    • key := 將s[i]作為整數

    • 在places[key]的末尾插入i

  • 對於t中的每個e，執行：

    • key := 將e作為整數

      • 如果places[key]為空，則

        • 返回False

      • i := places[key]的最後一個元素

      • 對於範圍從0到key - 1的j，執行：

        • 如果places[j]非空且places[j]的最後一個元素 < i，則

          • 返回False

      • 從places[key]中刪除最後一個元素

  • 返回True

示例

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

from collections import defaultdict
def solve(s, t):
   places = defaultdict(list)
   for i in reversed(range(len(s))):
      key = int(s[i])
      places[key].append(i)

   for e in t:
      key = int(e)
      if not places[key]:
         return False
      i = places[key][-1]
      for j in range(key):
         if places[j] and places[j][-1] < i:
            return False
      places[key].pop()
   return True

s = "95643"
t = "45963"
print(solve(s, t))

輸入

"95643", "45963"

輸出

True

更新於：2021年10月6日

91 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告