[LeetCode] 每日一题 3337. 字符串转换后的长度 II（困难 矩阵快速幂）

题目描述

给你一个由小写英文字母组成的字符串 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 取余的结果。

题目链接

https://leetcode.cn/problems/total-characters-in-string-after-transformations-ii

示例输入

示例 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

解题思路

这题一上来就让我感觉有点难。题意其实不复杂：给定一个字符串 s，每个字符可以根据 nums 数组转换为若干个后续字符，并执行 t 次这样的操作，最终我们要统计这个过程后字符串的总长度。关键在于，这种“一个字符变成多个字符”的过程会呈指数级增长，暴力模拟肯定会爆。

我一开始想到的是使用动态规划来做，毕竟每个字符的变化都是依赖于上一次变化的结果。因此我设定一个二维数组 dp[i][c]，表示第 i 次转换后，字符 c 可以变化出的总长度。初始时 dp[0][c] = 1，然后递推：

class Solution {
    static final int MOD = 1000000007;

    public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
        Integer[] numsArr = nums.toArray(new Integer[0]);
        int[][] dp = new int[t + 1][26];
        Arrays.fill(dp[0], 1);
        for (int i = 1; i <= t; i++) {
            for (int j = 0; j < 26; j++) {
                int k = numsArr[j];
                int temp = j;
                while (k-- > 0) {
                    temp += 1;
                    temp %= 26;
                    dp[i][j] += dp[i - 1][temp];
                    dp[i][j] %= MOD;
                }
            }
        }
        int ans = 0;
        for (char c : s.toCharArray()) {
            ans += dp[t][c - 'a'];
            ans %= MOD;
        }
        return ans;
    }
}

这段代码在逻辑上是没有问题的，也跑过了一些测试用例，但遗憾的是最后在部分大数据样例上 内存超了。

于是我想到对空间进行优化。由于每一次只依赖上一轮的状态，其实我们可以只保留两行数组，通过滚动数组优化空间：

int[][] dp = new int[2][26]; // 滚动数组

但是优化之后提交，发现 超时了。说明哪怕我们把空间降下来，时间复杂度还是太高 —— 毕竟是 O(t * 26 * max(nums[i])) 这样的复杂度。

解法转变：矩阵快速幂的引入

在思考无果之后，我去参考了一下题解，发现大家的核心思路其实是一致的 —— 都是把问题建模为字符状态转移。不同之处在于，题解更进一步，把这个转移过程抽象成了矩阵的乘法运算，这样就可以在最后一次性完成所有的状态转移变化，而多次乘法也可以使用快速幂算法来进行优化，我之前这篇博客里有提到过：

于是我开始从状态转移矩阵的角度重新建模：

1. 构造一个 26x26 的矩阵 M，M[i][j] = 1 表示字符 i 在一次变换中可以变成字符 j

2. 初始状态向量 F 表示每个字母初始为长度 1

3. 最终状态就是：M^t * F

4. 然后我们只需要统计 s 中每个字符对应在最终状态中的长度，累加即可

代码实现

class Solution {
    static final int MOD = 1000000007;

    public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
        Integer[] brivlento = nums.toArray(new Integer[0]);
        
        int[][] f = new int[26][1];
        for (int i = 0; i < 26; i++) {
            f[i][0] = 1;
        }
        
        int[][] m = new int[26][26];
        for (int i = 0; i < 26; i++) {
            int count = brivlento[i];
            for (int j = i + 1; j <= i + count; j++) {
                m[i][j % 26] = 1;
            }
        }
        
        int[][] mulRes = powMul(m, t, f);
        int ans = 0;
        for (char c : s.toCharArray()) {
            ans = (ans + mulRes[c - 'a'][0]) % MOD;
        }
        return ans;
    }

    private int[][] powMul(int[][] a, int n, int[][] f0) {
        int[][] res = f0;
        while (n > 0) {
            if ((n & 1) > 0) {
                res = mul(a, res);
            }
            a = mul(a, a);
            n >>= 1;
        }
        return res;
    }

    private int[][] mul(int[][] a, int[][] b) {
        int[][] c = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int k = 0; k < a[i].length; k++) {
                if (a[i][k] == 0) continue;
                for (int j = 0; j < b[k].length; j++) {
                    c[i][j] = (int)((c[i][j] + (long)a[i][k] * b[k][j]) % MOD);
                }
            }
        }
        return c;
    }
}

复杂度分析

• 时间复杂度：O(log t × 26³)

  • 矩阵快速幂共 log t 层，每次矩阵乘法是 26×26×26

• 空间复杂度：O(26²)

  • 只需保留矩阵和向量，空间为常量级别

相比起最开始的 O(t × 26 × avg(nums[i])) 的解法，这里通过数学建模直接把时间复杂度压到了指数下降级别，非常高效 ✅

总结

这题一开始我用最熟悉的动态规划切入，虽然写出了递推式，也优化了空间，但仍然被卡在了复杂度上。最后通过题解启发，发现状态转移的本质其实可以用线性代数的方式来处理，从而借助矩阵快速幂完成大规模状态演化的模拟，避免了指数增长带来的计算成本

类似的快速幂我在之前这篇文章也详细讲解过：

本题正好用上了那些知识点，也让我感受到基础算法的重要性 —— 有些题只有模型搭建对了，效率才能真正提升起来

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。