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

难度: Hard

给你两个字符串 s 和 t ，请你通过若干次以下操作将字符串 s 转化成字符串 t ：

选择 s 中一个非空子字符串并将它包含的字符就地升序排序。

比方说，对下划线所示的子字符串进行操作可以由 "14234" 得到 "12344" 。

如果可以将字符串 s 变成 t ，返回 true 。否则，返回 false 。

一个 子字符串 定义为一个字符串中连续的若干字符。

示例 1：

输入：s = "84532", t = "34852"
输出：true
解释：你可以按以下操作将 s 转变为 t ：
"84532" （从下标 2 到下标 3）-> "84352"
"84352" （从下标 0 到下标 2） -> "34852"

示例 2：

输入：s = "34521", t = "23415"
输出：true
解释：你可以按以下操作将 s 转变为 t ：
"34521" -> "23451"
"23451" -> "23415"

示例 3：

输入：s = "12345", t = "12435"
输出：false

示例 4：

输入：s = "1", t = "2"
输出：false

提示：

s.length == t.length
1 <= s.length <= 10⁵
s 和 t 都只包含数字字符，即 '0' 到 '9' 。

Submission

运行时间: 266 ms

内存: 20.0 MB

class Solution:
    def isTransformable(self, s: str, t: str) -> bool:

        pos = [deque([]) for _ in range(10)]
        for i, c in enumerate(s):
            pos[ord(c) - ord('0')].append(i)
        
        for i in range(len(t)):
            if len(pos[ord(t[i]) - ord('0')]) == 0:
                return False
            pivot = pos[ord(t[i]) - ord('0')].popleft()
            for j in range(ord(t[i]) - ord('0')):
                if len(pos[j]) > 0 and pos[j][0] < pivot:
                    return False

        return True

Explain

此题解的核心思路是利用索引队列跟踪字符串s中每个数字字符的位置。首先，为每个数字0-9创建一个队列来存储其在字符串s中出现的索引。遍历目标字符串t，对于t中的每个字符，检查其在s中的相应队列是否有索引可用。如果可用，取出最前面的索引（即位置最靠前的索引），并确保在这个索引之前，没有任何较小数字的索引存在。这样就可以确认s可以通过局部排序来匹配t的当前字符。如果在任意步骤发现条件不满足，即返回false。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def isTransformable(self, s: str, t: str) -> bool:

        # 初始化10个队列，对应数字0到9
        pos = [deque([]) for _ in range(10)]
        # 填充队列，记录每个数字在s中的所有索引
        for i, c in enumerate(s):
            pos[ord(c) - ord('0')].append(i)
        
        # 遍历目标字符串t
        for i in range(len(t)):
            # 获取当前字符对应的数字
            digit = ord(t[i]) - ord('0')
            # 如果该数字在s中无对应索引，返回False
            if len(pos[digit]) == 0:
                return False
            # 弹出当前数字的最前索引
            pivot = pos[digit].popleft()
            # 检查所有比当前数字小的数字的索引是否在pivot之前
            for j in range(digit):
                if len(pos[j]) > 0 and pos[j][0] < pivot:
                    return False

        # 如果所有字符检查完毕没有问题，则返回True
        return True

Explore

在题解中，我首先为数字0到9各初始化一个队列。然后遍历字符串s，对于s中的每个字符，我通过计算字符与'0'的ASCII码差值（即`ord(c) - ord('0')`），确定它代表的数字，并将它在s中的索引添加到对应数字的队列中。这样，每个数字的队列就按照在s中出现的顺序存储了所有的索引。后续在遍历字符串t时，可以直接从对应数字的队列中获取并使用这些索引。

使用队列来存储每个数字的索引是因为队列是先进先出（FIFO）的数据结构，这使得我们可以按照字符在字符串s中出现的顺序逐个处理它们。当遍历到字符串t的某个字符时，我们需要检查s中相应字符的出现顺序是否能够支持通过局部排序来匹配t。通过从队列中依次弹出索引，我们可以确保总是在处理s中当前可用的、位置最靠前的索引，从而正确地按照t的顺序重组s。

如果在处理字符串t时某个数字的队列为空，这意味着s中已经没有更多该数字的字符可以用来匹配t中当前位置的字符。由于我们必须用s中的字符按照t的顺序来重组s，缺少任何一个在t中需要的字符都会使得这一过程无法完成。因此，当发现任何一个必需的数字的索引用完（队列为空）时，直接返回false是因为已经不可能通过局部排序的方式将s重组成t了。

题解中的算法假设s和t都严格由数字字符组成。如果s或t包含非数字字符，或者两者字符种类不匹配，该算法将无法正确处理。在实际应用中，应首先验证s和t是否仅包含数字字符，并且字符种类相匹配。如果不符合这些前提条件，算法需要进行相应的调整或者报错处理，这通常需要根据具体的应用场景和需求来决定。