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
提示：
s.length == t.length1 <= s.length <= 10^5s和t仅由数字组成
解题思路
解题思路
这道题的关键在于理解排序操作的本质：排序操作不能改变字符的相对位置关系。具体来说，如果字符 a 在字符 b 的左边，且 a < b，那么排序后 a 仍然在 b 的左边。
核心观察
- 字符频次必须相同：
s和t中每个字符的出现次数必须完全相同 - 相对位置约束：对于每个字符，我们可以通过贪心策略来判断是否能够到达目标位置
贪心策略
我们从左到右遍历目标字符串 t，对于每个位置需要的字符：
- 在源字符串
s中找到最左边的该字符 - 检查是否可以通过排序操作将这个字符移动到当前位置
- 移动的关键限制：只能向左移动那些比当前字符大的字符
实现细节
使用队列记录每个数字在 s 中的所有位置，然后逐一匹配 t 中的字符。对于 t[i] 需要的字符 d：
- 从队列中取出字符
d的最左位置 - 检查在该位置右边是否存在比
d小的字符，如果存在则无法通过排序移动到前面
这种方法时间复杂度为 O(n)，空间复杂度为 O(n)。
代码实现
class Solution {
public:
bool isTransformable(string s, string t) {
vector<queue<int>> pos(10);
// 记录每个数字在s中的位置
for (int i = 0; i < s.length(); i++) {
pos[s[i] - '0'].push(i);
}
// 逐一匹配t中的字符
for (char c : t) {
int d = c - '0';
if (pos[d].empty()) return false;
int index = pos[d].front();
pos[d].pop();
// 检查是否有更小的数字在index右边
for (int smaller = 0; smaller < d; smaller++) {
if (!pos[smaller].empty() && pos[smaller].front() < index) {
return false;
}
}
}
return true;
}
};
class Solution:
def isTransformable(self, s: str, t: str) -> bool:
from collections import deque
# 记录每个数字在s中的位置
pos = [deque() for _ in range(10)]
for i, c in enumerate(s):
pos[int(c)].append(i)
# 逐一匹配t中的字符
for c in t:
d = int(c)
if not pos[d]:
return False
index = pos[d].popleft()
# 检查是否有更小的数字在index右边
for smaller in range(d):
if pos[smaller] and pos[smaller][0] < index:
return False
return True
public class Solution {
public bool IsTransformable(string s, string t) {
Queue<int>[] pos = new Queue<int>[10];
for (int i = 0; i < 10; i++) {
pos[i] = new Queue<int>();
}
// 记录每个数字在s中的位置
for (int i = 0; i < s.Length; i++) {
pos[s[i] - '0'].Enqueue(i);
}
// 逐一匹配t中的字符
foreach (char c in t) {
int d = c - '0';
if (pos[d].Count == 0) return false;
int index = pos[d].Dequeue();
// 检查是否有更小的数字在index右边
for (int smaller = 0; smaller < d; smaller++) {
if (pos[smaller].Count > 0 && pos[smaller].Peek() < index) {
return false;
}
}
}
return true;
}
}
var isTransformable = function(s, t) {
if (s.length !== t.length) return false;
// Count frequency of each digit
const sCount = new Array(10).fill(0);
const tCount = new Array(10).fill(0);
for (let i = 0; i < s.length; i++) {
sCount[s[i]]++;
tCount[t[i]]++;
}
// If frequencies don't match, transformation impossible
for (let i = 0; i < 10; i++) {
if (sCount[i] !== tCount[i]) return false;
}
// Store positions of each digit in s
const positions = new Array(10).fill(null).map(() => []);
for (let i = 0; i < s.length; i++) {
positions[s[i]].push(i);
}
// For each digit, track current index
const indices = new Array(10).fill(0);
// Process each character in t
for (let i = 0; i < t.length; i++) {
const digit = parseInt(t[i]);
if (indices[digit] >= positions[digit].length) {
return false;
}
const pos = positions[digit][indices[digit]];
// Check if any smaller digit appears after this position
// and hasn't been used yet
for (let smaller = 0; smaller < digit; smaller++) {
if (indices[smaller] < positions[smaller].length &&
positions[smaller][indices[smaller]] < pos) {
return false;
}
}
indices[digit]++;
}
return true;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 需要遍历字符串一次，每个字符的检查操作是常数时间 |
| 空间复杂度 | O(n) | 需要存储每个数字的位置信息 |