题目分析

这个题目难度较大，代码量很少，主要考察思路，如何寻找一种合适的数据结构表达这种关系非常重要。

队列

某个数前面比它小的数在变换后必须也要在它前面，这句话非常重要。
如s = “84532” t = “34852”
看t的第一个数字3，s的3前面没有比他小的数字，因此可以。
看t的第二个数字4，s的4前面没有比他小的数字，因此可以。
看t的第一个数字8，s的8前面没有比他小的数字，因此可以。
看t的第二个数字5，s的5前面有比他小的数字4，而t中5前面也有4，因此可以。
看t的第一个数字2，s的2前面没有比他小的数字，因此可以，输出True

下面看一个反例
如s = “12345” t = “12435”
看t的第一个数字1，s的1前面没有比他小的数字，因此可以。
看t的第二个数字2，s的2前面有比他小的数字1，而t中2前面也有1，因此可以。
看t的第一个数字4，s的3前面有比他小的数字1, 2和3，而t中2前面只有1和2，因此不可以，输出False

因此我们使用一个字典，其中键为0到9，值为队列，记录s每个数字出现的位置，然后遍历t。
对于t中的每一个数字k，如果k不存在于s中，则返回False。
如果存在s中，则寻找小于k的所有元素第一次出现的位置，如果在k前面，则输出False。
如果小于k的所有数字都不在k的前面，则说明这个元素可以移动到当前位置，则字典中对应的队列弹出队头元素。
当所有数字都比较完成后，则返回True。

每个数字最多比较10次，且要保存每个元素出现的索引，所以算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

from collections import deque


class Solution(object):
    def isTransformable(self, s, t):
        dic = {i: deque() for i in range(10)}
        for idx, val in enumerate(s):
            d = int(val)
            dic[d].append(idx)
        for idx, val in enumerate(t):
            d = int(val)
            if not dic[d]:
                return False
            if any(dic[j] and dic[j][0] < dic[d][0] for j in range(d)):
                return False
            dic[d].popleft()
        return True

刷题总结

这道题的代码就这么简短，但是思路难以想到。通过记录数字最早出现的位置，判断在某个数字前面是否有比它小的数字出现，通过队列保存数字出现的索引，方便从队头进行删除，太精彩了。