在Python中检查字符串是否可通过子字符串排序操作进行转换的程序

假设我们有两个数字字符串s和t，我们想要通过以下操作使字符串s转换为t，任意次数：1. 选择一个非空子字符串在原地对其进行排序，使字符按升序排列。我们必须检查是否可能将字符串s转换为字符串t。

因此，如果输入是s =“95643”t =“45963”，则输出将是True，因为我们可以使用如“95643” – & gt;“95463” – & gt;“45963”的方式将s转换为t。

为了解决这个问题，我们将按照以下步骤进行 –

places：默认值类型为列表的映射
对于i在区间[size of s, 0]中，做以下循环：
- key：将s[i]解析成整数
- 将i插入到places[key]的末尾
对于t中的每个e，执行以下操作
- key：将e解析成整数
  - 如果places[key]为空，则
  - 返回False
  - i：places[key]的最后一个元素
  - 对于j在区间[0，key – 1]中，做以下循环
  - 如果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))