数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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 次浏览
广告