用Python中的子字符串排序操作检查字符串是否可转换的程序
假设我们有两个数字字符串s和t,我们希望使用以下操作任意次数将字符串s转换为t:1.在s中选择一个非空子字符串并就地排序,使字符按升序排列。我们必须检查是否可以将字符串s转换为字符串t。
因此,如果输入类似于s="95643"t="45963",那么输出将为True,因为我们可以使用"95643"->"95463"->"45963"将s转换为t。
示例
让我们看下面的实现来更好地理解
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