Given two strings s and t, transform string s into string t using the following operation any number of times:
Choose a non-empty substring in s and sort it in place so the characters are in ascending order.
For example, applying the operation on the underlined substring in “14234” results in “12344”.
Return true if it is possible to transform s into t. Otherwise, return false.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = “84532”, t = “34852”
Output: true
Explanation: You can transform s into t using the following sort operations:
“84532” (from index 2 to 3) -> “84352”
“84352” (from index 0 to 2) -> “34852”
Example 2:
Input: s = “34521”, t = “23415”
Output: true
Explanation: You can transform s into t using the following sort operations:
“34521” -> “23451”
“23451” -> “23415”
Example 3:
Input: s = “12345”, t = “12435”
Output: false
Constraints:
- s.length == t.length
- 1 <= s.length <= 105
- s and t consist of only digits.
整体思路就是依次从 t 中取出数字， 然后从 s 中找出该数字目前最早出现的位置， 然后看从这个位置能不能移动到 s 的最左侧， 如果不行则证明没法通过排序的方法获得到 t, 如果可以的话则把该位置上的数字删除。
但是实际按上述思路来实现的话肯定会超时， 我们需要用其他方法来辅助我们来进行上述操作。
首先， 一个数字要想向左移动， 那它左侧的数字一定是要大于它的， 如果中途出现了比它小的数字， 那它一定移动不到目标位置。
其次， 因为 s 和 t 都是由 0-9 组成的， 所以我们可以很方便的得到 s[i]之前 0-9 每个数字的计数。代表 s[i]之前 0-9 每个数字的出现次数。
因为我们是正向遍历 t, 所以每次都是从 s 中挑选数字移动到最左侧， 因为移动到左侧的已经处于正确的位置了， 所以下一次移动不用考虑这些已经移动到正确位置的数字， 相当于我们已经把这些数字移除了， 我们每次都把数字移动到最左侧就可以了。 能不能移动到最左侧在我们上面的计数中表达出来就是, 对于 0<i<t[j], 所有 prev_counts[i] <= 0。 之所以是<=0 而不是==0, 我们马上讲到。
能不能向左移动的检查我们解决了， 然后就是第二件事， 因为我们把这些数字从 s 中移动到正确的位置相当于把这些数字删除了， 所以 prev_counts 在整个过程中不是固定的， 我们每移动完一个数字， 理论上我们需要变更 prev_counts 以使其能正确的映射当前剩余数字的情况, 但因为我们计的是前面出现的数字数量， 理论上我们每移动完一个数字需要把该数字之后的所有计数都修改掉。但是这样还是躲不过超时。所以我们换一种办法， 我们记录到目前为止已经移除的 0-9 每个数字的数量 removed_counts， 每移动完一个数字就更新一次， 检查下一个数字的时候， 我们把该数字的 prev_counts 中的每一位减去 removed_counts 中的每一位， 实际得到的就是有效的 prev_counts。之所以说是有效的而不是真实的， 是因为可能会出现过减的情况, 计数会变成负数，这也是为什么前面是<=0 而不是==0 的原因。但是这对我们的检查没有什么影响, 出现这种情况只是说明前面的步骤处理了此时 s[i]右侧的数字而已。举个例子:
“43” => “34”
s[0] = 4 因为是第一个数字，所以前面没有任何数字
s[1] = 3 前面有个 4
所以:
prev_counts = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]
removed_counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
第一步先移动 3
actual_prev_counts = prev_counts[1] - removed_counts = [0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
actual_prev_counts[0…3]都是 0， 也就是 3 之前没有比它小的数字， 可以移动
removed_counts = [0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
第二步移动 4
actual_prev_counts = prev_counts[0] - removed_counts = [0, 0, 0, -1, 0, 0, 0, 0, 0, 0]
actual_prev_counts[0…4]都是<=0 的， 也就是 3 之前没有比它小的数字， 可以移动
removed_counts = [0, 0, 0, 1, 1, 0, 0, 0, 0, 0]
完成
use std::collections::HashMap;
impl Solution {
pub fn is_transformable(s: String, t: String) -> bool {
let s_char_counts = s.chars().fold(vec![0; 10], |mut l, c| {
l[c.to_string().parse::<usize>().unwrap()] += 1;
l
});
let t_char_counts = t.chars().fold(vec![0; 10], |mut l, c| {
l[c.to_string().parse::<usize>().unwrap()] += 1;
l
});
for i in 0..10 {
if s_char_counts[i] != t_char_counts[i] {
return false;
}
}
let mut prev_count_set: Vec<Vec<i32>> = s
.chars()
.scan(vec![0; 10], |s, c| {
s[c.to_string().parse::<usize>().unwrap()] += 1;
Some(s.clone())
})
.collect();
prev_count_set.pop();
prev_count_set.insert(0, vec![0; 10]);
let mut positions: HashMap<char, Vec<usize>> =
s.chars().enumerate().fold(HashMap::new(), |mut m, (i, c)| {
m.entry(c).or_insert(Vec::new()).push(i);
m
});
let mut moved = vec![0; 10];
for c in t.chars() {
let n = c.to_string().parse::<usize>().unwrap();
if let Some(ps) = positions.get_mut(&c) {
let p = ps.remove(0);
let prevs = &prev_count_set[p];
for i in 0..10 {
if i == n {
break;
}
if prevs[i] - moved[i] > 0 {
return false;
}
}
moved[n] += 1;
}
}
true
}
}