class Solution {
public:
bool isTransformable(string s, string t) {
}
};
1585. 检查字符串是否可以通过排序子字符串得到另一个字符串
给你两个字符串 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.length1 <= s.length <= 105s 和 t 都只包含数字字符，即 '0' 到 '9' 。原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 7.2 MB, 提交时间: 2023-09-23 00:47:03
func isTransformable(s string, t string) bool {
posMap := make([][]int, 10)
for i := 0; i < len(s); i++ {
posMap[int(s[i]-'0')] = append(posMap[int(s[i]-'0')], i) //记录s中每个字符出现的位置
}
//对于t中的每个字符 判断
for i := 0; i < len(t); i++ {
num := int(t[i] - '0')
pos := posMap[num]
if len(pos) == 0 { //在s中没有对应的字符 肯定无法完成
return false
}
// t[i]在s中的第一个出现位置 pos[0]
// 判断s中，是否有比num小的出现在pos[0]之前，挡住了移动的道路
for j := 0; j < num; j++ {
//如果数字j在s中的第一个位置在 pos[0]前面，挡住了移动的道路
if len(posMap[j]) > 0 && posMap[j][0] < pos[0] {
return false
}
//如果数字j在s中的第一个位置在 pos[0]后面，由于posMap是单调递增的，所以数字j在s中的位置肯定都是大于pos[0]的
}
//s中，比num小的数字都在pos[0]后面
posMap[num] = pos[1:]
}
return true
}
java 解法, 执行用时: 35 ms, 内存消耗: 47.2 MB, 提交时间: 2023-09-23 00:46:39
class Solution {
public boolean isTransformable(String s, String t) {
int n = s.length();
Queue<Integer>[] pos = new Queue[10];
for (int i = 0; i < 10; ++i) {
pos[i] = new LinkedList<Integer>();
}
for (int i = 0; i < n; ++i) {
pos[s.charAt(i) - '0'].offer(i);
}
for (int i = 0; i < n; ++i) {
int digit = t.charAt(i) - '0';
if (pos[digit].isEmpty()) {
return false;
}
for (int j = 0; j < digit; ++j) {
if (!pos[j].isEmpty() && pos[j].peek() < pos[digit].peek()) {
return false;
}
}
pos[digit].poll();
}
return true;
}
}
cpp 解法, 执行用时: 76 ms, 内存消耗: 18.3 MB, 提交时间: 2023-09-23 00:46:23
class Solution {
public:
bool isTransformable(string s, string t) {
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 digit = t[i] - '0';
if (pos[digit].empty()) {
return false;
}
for (int j = 0; j < digit; ++j) {
if (!pos[j].empty() && pos[j].front() < pos[digit].front()) {
return false;
}
}
pos[digit].pop();
}
return true;
}
};
python3 解法, 执行用时: 604 ms, 内存消耗: 20.4 MB, 提交时间: 2023-09-23 00:46:17
class Solution:
# 冒泡排序
def isTransformable(self, s: str, t: str) -> bool:
n = len(s)
pos = {i: collections.deque() for i in range(10)}
for i, digit in enumerate(s):
pos[int(digit)].append(i)
for i, digit in enumerate(t):
d = int(digit)
if not pos[d]:
return False
if any(pos[j] and pos[j][0] < pos[d][0] for j in range(d)):
return False
pos[d].popleft()
return True