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

开启你的职业生涯

完成课程获得认证

开始学习
广告