问题描述给定一个由小写英文字母组成的字符串 s、一个整数 t转换次数以及一个长度为 26 的数组 nums。每次转换时字符串中的每个字符 s[i] 都会替换为字母表中它后面连续的 nums[s[i] - a] 个字符如果超出 z 则回绕到字母表开头。例如a 且 nums[0] 3则 a 转换为 bcdy 且 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 实现rustconst MOD: i64 1_000_000_007;const SIZE: usize 26;impl Solution {pub fn length_after_transformations(s: String, t: i32, nums: Veci32) - i32 {let t t as usize;// 1. 统计初始字符串中每个字符的出现次数let mut count vec![0i64; SIZE];for ch in s.chars() {count[(ch as u8 - ba) 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 * powerlet 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: VecVeci64, b: VecVeci64) - VecVeci64 {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: VecVeci64, mut exp: usize) - VecVeci64 {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)用于存储矩阵。
DeepSeek 深度思考 LeetCode 3337. 字符串转换后的长度 II Rust实现
问题描述给定一个由小写英文字母组成的字符串 s、一个整数 t转换次数以及一个长度为 26 的数组 nums。每次转换时字符串中的每个字符 s[i] 都会替换为字母表中它后面连续的 nums[s[i] - a] 个字符如果超出 z 则回绕到字母表开头。例如a 且 nums[0] 3则 a 转换为 bcdy 且 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 实现rustconst MOD: i64 1_000_000_007;const SIZE: usize 26;impl Solution {pub fn length_after_transformations(s: String, t: i32, nums: Veci32) - i32 {let t t as usize;// 1. 统计初始字符串中每个字符的出现次数let mut count vec![0i64; SIZE];for ch in s.chars() {count[(ch as u8 - ba) 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 * powerlet 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: VecVeci64, b: VecVeci64) - VecVeci64 {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: VecVeci64, mut exp: usize) - VecVeci64 {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)用于存储矩阵。
