题目描述

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

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

比方说，对括号所示的子字符串进行操作可以由 "1(4234)" 得到 "1(2344)"。

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

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

样例

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

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

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

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

限制

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

算法

(逆序，冒泡排序) $O(n)$

1. 题目中的操作与每次操作相邻的两个数字等价，所以这个过程可以看做是一个冒泡排序的过程。
2. 考虑 $t$ 中的第一个数字 d，其一定是从 $s$ 中的最近的 d 排序过来的。假设 d 在 $s$ 中的坐标为 $j$，现在需要保证从 $s(0)$ 到 $s(j-1)$ 中不存在一个数字比 d 小，否则就无法排序 d 到最开头。
3. 如果可以将 d 排到 $t$ 的最开头。则考虑下一个新的数字，以及其在 $s$ 中的位置，同时判断能否排序时，也无需再考虑上上一个 d。
4. 初始化 10 个队列，每个队列中记录当前队列所代表的数字在 $s$ 中的位置。然后遍历字符串 $t$，按照以上规则判断即可。

时间复杂度

• 初始化队列的时间复杂度为 $O(n)$。字符串 $t$ 遍历一次，遍历时每个位置最多枚举 10 个数字，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储队列。

C++ 代码

class Solution {
public:
    bool isTransformable(string s, string t) {
        const int n = s.size();
        vector<queue<int>> pos(10);
        for (int i = 0; i < n; i++) {
            pos[s[i] - '0'].push(i);
        }

        for (int i = 0; i < n; i++) {
            int x = t[i] - '0';
            if (pos[x].empty()) return false;

            for (int y = 0; y < x; y++)
                if (!pos[y].empty() && pos[y].front() < pos[x].front())
                    return false;

            pos[x].pop();
        }

        return true;
    }
};