LC 1585. 检查字符串是否可以通过排序子字符串得到另一个字符串

https://leetcode-cn.com/problems/check-if-string-is-transformable-with-substring-sort-operations/

这题很容易想去做排序，但是重复排序一方面会造成太多不要计算，同时会打乱之前创建好的索引，另外寻找排序的区间也是一个很大的问题。

但是如果换个角度，我们只关心能否将每个数字各就其位的话，就简单多了。如果一个数字不匹配，那么就去后面找这个数字，让这个数字提前。 但是因为提前的方法是排序，所以必须确保，从当前数字到期望找到的数字中间，没有更小的数字出现。

以 s = "84532", t = "34852" 为例 

class Solution:
    def isTransformable(self, s: str, t: str) -> bool:
        pos = [[] for _ in range(10)]
        for i in reversed(range(len(s))):
            c = ord(s[i]) - ord('0')
            pos[c].append(i)

        for i in range(len(t)):
            c = ord(t[i]) - ord('0')
            if not pos[c]: return False
            p = pos[c][-1]
            pos[c].pop()
            # 确保没有更小的数在这个位置之前
            for j in range(c):
                if not pos[j]: continue
                if pos[j][-1] < p: return False

        return True