题目描述

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

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

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

如果可以将字符串 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 <= 105
• s 和 t 都只包含数字字符，即 '0' 到 '9' 。

算法分析

对于 选择一个区间进行排序 的探究

• 1、选择一个长度是2的区间进行排序 ==> 选择两个相邻字符进行排序
• 2、选择相邻的字符排序排一个区间，可以通过若干次排序两个字符 ==> 选择一个区间进行排序
  因此，选择一个区间排序的效果 可以拆分成若干个 选择两个相邻字符进行排序的效果
  因此，选择一个区间进行排序 直接看成 选择两个相邻的字符进行排序 （冒泡排序的本质）

对于某个原串S和目标串T，x代表任意数
S: a x x x
T: x x x a
若想将S中a元素(位置是i)排序到T中a元素的位置（位置是j），必须满足在原串S中i到j之间不存在比a大的数即可

操作：

• 1、开10个栈，编号是0到9，存的是每个数字在原串S中的位置
• 2、从前往后，将原串S中的数字加入到相应的栈中
• 3、从后后往前枚举目标串T，当枚举到c数字时，拿到S串中在前面离它最近的c数字的位置p，保证p位置到当前位置不存在比c大的数即可，因此判断[c + 1,9]数字中是否存在坐标在[p,i]的位置，若存在，则return false
• 4、若都一直平安无事，则return true

时间复杂度 $O(n)$

Java 代码

class Solution {
    public boolean isTransformable(String s, String t) {
        Stack[] pos = new Stack[10];
        for(int i = 0;i < 10;i ++)
            pos[i] = new Stack<Integer>();

        int n = s.length();
        for(int i = 0;i < n;i ++)
        {
            pos[s.charAt(i) - '0'].add(i);
        }

        for(int i = n - 1;i >= 0;i --)
        {
            int c = t.charAt(i) - '0';
            if(pos[c].size() == 0) return false;//当两个字符串的元素不对应时
            int p = (int) pos[c].pop();
            for(int j = c + 1;j < 10;j ++)
            {
                if(pos[j].size() > 0 && p < (int)pos[j].peek())
                    return false;
            }
        }
        return true;
    }
}