目标
给你一个由小写英文字母组成的字符串 s，一个整数 t 表示要执行的 转换 次数，以及一个长度为 26 的数组 nums。每次 转换 需要根据以下规则替换字符串 s 中的每个字符：
- 将 s[i] 替换为字母表中后续的 nums[s[i] - 'a'] 个连续字符。例如，如果 s[i] = 'a' 且 nums[0] = 3，则字符 'a' 转换为它后面的 3 个连续字符，结果为 "bcd"。
- 如果转换超过了 'z'，则 回绕 到字母表的开头。例如，如果 s[i] = 'y' 且 nums[24] = 3，则字符 'y' 转换为它后面的 3 个连续字符，结果为 "zab"。
返回 恰好 执行 t 次转换后得到的字符串的 长度。
由于答案可能非常大，返回其对 10^9 + 7 取余的结果。
示例 1：
输入： s = "abcyy", t = 2, nums = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]
输出： 7
解释：
第一次转换 (t = 1)
'a' 变为 'b' 因为 nums[0] == 1
'b' 变为 'c' 因为 nums[1] == 1
'c' 变为 'd' 因为 nums[2] == 1
'y' 变为 'z' 因为 nums[24] == 1
'y' 变为 'z' 因为 nums[24] == 1
第一次转换后的字符串为: "bcdzz"
第二次转换 (t = 2)
'b' 变为 'c' 因为 nums[1] == 1
'c' 变为 'd' 因为 nums[2] == 1
'd' 变为 'e' 因为 nums[3] == 1
'z' 变为 'ab' 因为 nums[25] == 2
'z' 变为 'ab' 因为 nums[25] == 2
第二次转换后的字符串为: "cdeabab"
字符串最终长度： 字符串为 "cdeabab"，长度为 7 个字符。示例 2：
输入： s = "azbk", t = 1, nums = [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
输出： 8
解释：
第一次转换 (t = 1)
'a' 变为 'bc' 因为 nums[0] == 2
'z' 变为 'ab' 因为 nums[25] == 2
'b' 变为 'cd' 因为 nums[1] == 2
'k' 变为 'lm' 因为 nums[10] == 2
第一次转换后的字符串为: "bcabcdlm"
字符串最终长度： 字符串为 "bcabcdlm"，长度为 8 个字符。说明：
- 1 <= s.length <= 10^5
- s 仅由小写英文字母组成。
- 1 <= t <= 10^9
- nums.length == 26
- 1 <= nums[i] <= 25
思路
对字符串执行 t 次转换，求字符串的最终长度。每次转换需要将字符 s[i] 转换为字母表中后面的 nums[s[i] - 'a'] 个连续字符，如果超过了 z 则回到字母表开头。
与 3335.字符串转换后的长度I 的区别是替换为后面的连续 nums[s[i] - 'a'] 个字符。
定义 dp[k][i] 表示第 k 次转换后，字符 (char)(i + 'a') 的出现次数。但是转换次数高达 10^9 会超出内存限制。
转换次数太大，必须想办法降低它的复杂度。想到了倍增与快速幂，可以使用矩阵描述每一次字符的转换，考虑矩阵快速幂。
定义矩阵 matrix 的第 i 行表示字母 (char)(i + 'a') 转换后的字符集合，使用行向量表示， 第 j 列为 1 表示转换后的字母为 (char)(j + 'a')。于是问题转换为 vector * matrix^t，其中 vector 表示字符串每个字符的出现次数。
代码
/**
* @date 2025-05-14 8:56
*/
public class LengthAfterTransformations3337 {
public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
int mod = 1000000007;
int[] vector = new int[26];
char[] chars = s.toCharArray();
for (char c : chars) {
vector[c - 'a']++;
}
int[][] matrix = new int[26][26];
for (int i = 0; i < 26; i++) {
for (int j = 1; j <= nums.get(i); j++) {
int index = (i + j) % 26;
matrix[i][index] = 1;
}
}
int[] cnt = pow(vector, matrix, t, mod);
int res = 0;
for (int num : cnt) {
res = (res + num) % mod;
}
return res;
}
public int[] pow(int[] vector, int[][] matrix, int exponent, int mod) {
int[] res = vector;
while (exponent > 0) {
if ((exponent & 1) == 1) {
res = multiply(res, matrix, mod);
}
matrix = square(matrix, mod);
exponent >>= 1;
}
return res;
}
public int[][] square(int[][] matrix, int mod) {
int n = matrix.length;
int[][] res = new int[n][n];
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
for (int i = 0; i < n; i++) {
res[row][col] = (int) ((res[row][col] + (long) matrix[row][i] * matrix[i][col]) % mod);
}
}
}
return res;
}
public int[] multiply(int[] vector, int[][] matrix, int mod) {
int n = vector.length;
int[] res = new int[n];
for (int col = 0; col < n; col++) {
for (int i = 0; i < n; i++) {
res[col] = (int) ((res[col] + (long) vector[i] * matrix[i][col]) % mod);
}
}
return res;
}
}
性能
