Python程式檢查兩個字串之間是否存在字典序更大的排列

假設我們有兩個相同大小的字串 s 和 t，我們需要檢查是否存在 s 的某個排列 s1 和 t 的某個排列 t1，使得：對於所有 0 ≤ i < n，s1[i] ≤ t1[i] 或對於所有 0 ≤ i < n，t1[i] ≤ s1[i]。

因此，如果輸入類似於 s = "vyx" t = "wzx"，則輸出將為 True，因為我們可以有 s1 = "vxy" 和 t1 = "wxz"。

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

• 如果 s 和 t 為空，則
  • 返回 True
• s := 對字串 s 進行排序
• t := 對字串 t 進行排序
• 定義一個函式 util()。它將接收 s1 和 s2 作為引數。
• 對於範圍從 0 到 s1 大小的 i，執行以下操作：
  • 如果 s1[i] > t1[i]，則
    • 返回 False
• 返回 True
• 從主方法執行以下操作：
• 如果 util(s, t) 為真，則
  • 返回 True
• 交換 s 和 t
• 返回 util(s, t)

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

示例

 即時演示

class Solution:
   def solve(self, s, t):
      if not len(s) or not len(t):
         return True
         s = sorted(s)
         t = sorted(t)
   def util(s1, t1):
      for i in range(len(s1)):
         if s1[i] > t1[i]:
            return False
         return True
         if util(s, t):
            return True
      s, t = t, s
      return util(s, t)
ob = Solution()
s = "vyx"
t = "wzx"
print(ob.solve(s, t))

輸入

"vyx", "wzx"

輸出

True

Arnab Chakraborty

更新於: 2020-11-19

89 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習