Kimi 思考 LeetCode 3337. 字符串转换后的长度 II Java实现
以下是 LeetCode 3337「字符串转换后的长度 II」的 Java 实现，采用矩阵快速幂优化递推：
```java
import java.util.List;
class Solution {
private static final int MOD = (int) 1e9 + 7;
private static final int M = 26;
public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
// 统计初始字符串中每个字母的出现次数
int[] cnt = new int[M];
for (char c : s.toCharArray()) {
cnt[c - 'a']++;
}
// 构建 26x26 的转移矩阵
// matrix[i][j] = 1 表示字母 i 经过一次转换可以变成字母 j
int[][] matrix = new int[M][M];
for (int i = 0; i < M; i++) {
int num = nums.get(i);
for (int j = 1; j <= num; j++) {
matrix[i][(i + j) % M] = 1;
}
}
// 计算转移矩阵的 t 次幂
int[][] factor = matpow(matrix, t);
// 向量乘以矩阵
int[] result = vectorMatrixMultiply(cnt, factor);
// 最终答案为所有字母数量之和
int ans = 0;
for (int val : result) {
ans = (ans + val) % MOD;
}
return ans;
}
// 矩阵乘法（带模运算，跳过0元素优化）
private int[][] matmul(int[][] a, int[][] b) {
int n = a.length;
int p = b.length;
int q = b[0].length;
int[][] res = new int[n][q];
for (int i = 0; i < n; i++) {
for (int k = 0; k < p; k++) {
if (a[i][k] == 0) continue;
for (int j = 0; j < q; j++) {
res[i][j] = (int) ((res[i][j] + 1L * a[i][k] * b[k][j]) % MOD);
}
}
}
return res;
}
// 矩阵快速幂
private int[][] matpow(int[][] mat, int power) {
int[][] res = new int[M][M];
// 初始化为单位矩阵
for (int i = 0; i < M; i++) {
res[i][i] = 1;
}
while (power > 0) {
if ((power & 1) != 0) {
res = matmul(res, mat);
}
mat = matmul(mat, mat);
power >>= 1;
}
return res;
}
// 行向量（1x26）乘以矩阵（26x26）
private int[] vectorMatrixMultiply(int[] vector, int[][] matrix) {
int[] result = new int[M];
for (int i = 0; i < M; i++) {
long sum = 0;
for (int j = 0; j < M; j++) {
sum = (sum + 1L * vector[j] * matrix[j][i]) % MOD;
}
result[i] = (int) sum;
}
return result;
}
}
```
核心思路
1. 状态定义：令 `f[i][j]` 表示经过 `i` 次转换后，第 `j` 个字母（`a`=0, ..., `z`=25）的个数。初始时 `f[0][j]` 就是字符串 `s` 中各字母的频次。
2. 转移矩阵：构造一个 26×26 的矩阵 `matrix`，其中 `matrix[i][j] = 1` 当且仅当字母 `i` 经过一次转换能生成字母 `j`。根据题意，字母 `i` 会生成 `nums[i]` 个后续连续字母（循环），即 `i+1, i+2, ..., i+nums[i]`（模 26）。
3. 矩阵快速幂：由于 `t` 最大可达 `10^9`，直接递推会超时。利用矩阵乘法的结合律，通过快速幂在 `O(log t × 26³)` 的时间内计算出 `matrix^t`。
4. 计算结果：初始频次向量（1×26）乘以 `matrix^t`，得到 `t` 次转换后的各字母数量，求和即为最终字符串长度。
复杂度
- 时间复杂度：`O(|s| + log t × 26³)`，其中 `|s| ≤ 10⁵`
- 空间复杂度：`O(26²)`，即常数级空间