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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习