DeepSeek 深度思考 LeetCode 3337. 字符串转换后的长度 II Rust实现
问题描述
给定一个由小写英文字母组成的字符串 s、一个整数 t（转换次数）以及一个长度为 26 的数组 nums。每次转换时，字符串中的每个字符 s[i] 都会替换为字母表中它后面连续的 nums[s[i] - 'a'] 个字符，如果超出 'z' 则回绕到字母表开头。
例如，'a' 且 nums[0] = 3，则 'a' 转换为 "bcd"；'y' 且 nums[24] = 3，则 'y' 转换为 "zab"。要求返回恰好执行 t 次转换后字符串的长度，结果对 10^9 + 7 取模。
算法思路
核心思想：使用矩阵快速幂优化转换过程。
1. 状态表示：用一个长度为 26 的向量 count 表示当前每种字符的出现次数。
2. 构建转移矩阵：构建一个 26 x 26 的矩阵 M，其中 M[i][j] = 1 表示字符 i 经过一次转换会产生一个字符 j。
3. 计算转移矩阵的 t 次幂：利用快速幂计算 M^t。
4. 计算最终状态：将初始计数向量与 M^t 相乘，得到最终每种字符的计数。
5. 求和：将最终计数向量的所有元素相加，得到最终字符串长度。
Rust 实现
```rust
const MOD: i64 = 1_000_000_007;
const SIZE: usize = 26;
impl Solution {
pub fn length_after_transformations(s: String, t: i32, nums: Vec<i32>) -> i32 {
let t = t as usize;
// 1. 统计初始字符串中每个字符的出现次数
let mut count = vec![0i64; SIZE];
for ch in s.chars() {
count[(ch as u8 - b'a') as usize] += 1;
}
// 2. 构建转移矩阵
let mut matrix = vec![vec![0i64; SIZE]; SIZE];
for i in 0..SIZE {
let num = nums[i] as usize;
for j in 1..=num {
let idx = (i + j) % SIZE;
matrix[i][idx] = 1;
}
}
// 3. 计算转移矩阵的 t 次幂
let power = Self::matrix_pow(&matrix, t);
// 4. 计算最终计数向量: count * power
let mut final_count = vec![0i64; SIZE];
for i in 0..SIZE {
for j in 0..SIZE {
final_count[i] = (final_count[i] + count[j] * power[j][i]) % MOD;
}
}
// 5. 求和得到最终长度
let mut ans = 0;
for &val in &final_count {
ans = (ans + val) % MOD;
}
ans as i32
}
// 矩阵乘法
fn matrix_mul(a: &Vec<Vec<i64>>, b: &Vec<Vec<i64>>) -> Vec<Vec<i64>> {
let n = a.len();
let mut res = vec![vec![0i64; n]; n];
for i in 0..n {
for k in 0..n {
if a[i][k] == 0 {
continue;
}
let aik = a[i][k];
for j in 0..n {
res[i][j] = (res[i][j] + aik * b[k][j]) % MOD;
}
}
}
res
}
// 矩阵快速幂
fn matrix_pow(mat: &Vec<Vec<i64>>, mut exp: usize) -> Vec<Vec<i64>> {
let n = mat.len();
// 初始化为单位矩阵
let mut res = vec![vec![0i64; n]; n];
for i in 0..n {
res[i][i] = 1;
}
let mut base = mat.clone();
while exp > 0 {
if exp & 1 == 1 {
res = Self::matrix_mul(&res, &base);
}
base = Self::matrix_mul(&base, &base);
exp >>= 1;
}
res
}
}
```
代码说明
· matrix_mul：优化了矩阵乘法，跳过零元素以提高效率。
· matrix_pow：实现了二进制快速幂，将 O(t) 的转换次数优化为 O(log t)。
· 向量与矩阵相乘：注意乘法顺序，最终计数向量 = 初始计数向量 × M^t。
复杂度分析
· 时间复杂度：O(SIZE^3 * log t)，其中 SIZE = 26 是常数，因此实际为 O(log t)。
· 空间复杂度：O(SIZE^2)，用于存储矩阵。