分类： leetcode

目标

给你一个由小写英文字母组成的字符串 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;
    }

}

性能