1585. Check If String Is Transformable With Substring Sort Operations¶
题目信息¶
- 题号:
1585
- 难度:
Hard
- 主题:
字符串、贪心、位置队列
- 原题:
- 重点:
每次可把任意连续子串按升序排序;较大数字可被较小数字越过,但较小数字不能越过仍在前方的更小数字
题目重述¶
给定长度相同的数字字符串 s 和 t。一次操作可以选择 s 的任意非空连续子串,并把该子串中的字符按非递减顺序排序。
可以执行任意次数操作。请判断是否能够把 s 变成 t。
1 <= s.length == t.length <= 10^5,两个字符串只包含数字字符。
自建示例¶
排序整个字符串可以直接得到目标:
输入:s = "845", t = "458"
输出:true
解释:把整个字符串按升序排序即可。
升序操作不能把较大数字移到较小数字前方:
输入:s = "12", t = "21"
输出:false
解释:任何子串升序排序都无法把已经有序的 12 变成 21。