LeetCode 3337.字符串转换后的长度 II：矩阵快速幂(也没有想象中的那么高级啦)

【LetMeFly】3337.字符串转换后的长度 II：矩阵快速幂(也没有想象中的那么高级啦)

力扣题目链接：https://leetcode.cn/problems/total-characters-in-string-after-transformations-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 次转换后得到的字符串的 长度。

由于答案可能非常大，返回其对 109 + 7 取余的结果。

示例 1：

输出： 7

解释：

• 第一次转换 (t = 1)

  <ul>
  	<li><code>'a'</code> 变为 <code>'b'</code> 因为 <code>nums[0] == 1</code></li>
  	<li><code>'b'</code> 变为 <code>'c'</code> 因为 <code>nums[1] == 1</code></li>
  	<li><code>'c'</code> 变为 <code>'d'</code> 因为 <code>nums[2] == 1</code></li>
  	<li><code>'y'</code> 变为 <code>'z'</code> 因为 <code>nums[24] == 1</code></li>
  	<li><code>'y'</code> 变为 <code>'z'</code> 因为 <code>nums[24] == 1</code></li>
  	<li>第一次转换后的字符串为: <code>"bcdzz"</code></li>
  </ul>
  </li>
  <li>
  <p><strong>第二次转换 (t = 2)</strong></p>
  
  <ul>
  	<li><code>'b'</code> 变为 <code>'c'</code> 因为 <code>nums[1] == 1</code></li>
  	<li><code>'c'</code> 变为 <code>'d'</code> 因为 <code>nums[2] == 1</code></li>
  	<li><code>'d'</code> 变为 <code>'e'</code> 因为 <code>nums[3] == 1</code></li>
  	<li><code>'z'</code> 变为 <code>'ab'</code> 因为 <code>nums[25] == 2</code></li>
  	<li><code>'z'</code> 变为 <code>'ab'</code> 因为 <code>nums[25] == 2</code></li>
  	<li>第二次转换后的字符串为: <code>"cdeabab"</code></li>
  </ul>
  </li>
  <li>
  <p><strong>字符串最终长度：</strong> 字符串为 <code>"cdeabab"</code>，长度为 7 个字符。</p>
  </li>
  

示例 2：

输出： 8

解释：

• 第一次转换 (t = 1)

  <ul>
  	<li><code>'a'</code> 变为 <code>'bc'</code> 因为 <code>nums[0] == 2</code></li>
  	<li><code>'z'</code> 变为 <code>'ab'</code> 因为 <code>nums[25] == 2</code></li>
  	<li><code>'b'</code> 变为 <code>'cd'</code> 因为 <code>nums[1] == 2</code></li>
  	<li><code>'k'</code> 变为 <code>'lm'</code> 因为 <code>nums[10] == 2</code></li>
  	<li>第一次转换后的字符串为: <code>"bcabcdlm"</code></li>
  </ul>
  </li>
  <li>
  <p><strong>字符串最终长度：</strong> 字符串为 <code>"bcabcdlm"</code>，长度为 8 个字符。</p>
  </li>
  

提示：

• 1 <= s.length <= 105
• s 仅由小写英文字母组成。
• 1 <= t <= 109
• nums.length == 26
• 1 <= nums[i] <= 25

解题方法：矩阵快速幂

鸣谢灵茶山艾府的题解矩阵快速幂优化 DP

先计算一个字符a进行$t$次替换后的长度、一个b进行$t$次替换后的长度、…、一个z进行$t$次替换后的长度。每个字母进行$t$次替换后字符串长度计算出来后，只需要统计一下原始字符串中每种字符分别有多少个，乘一下就好了。

如何计算a进行$t$次替换后的长度？

假设a进行一次替换得到b和c，那么问题就变成了b进行$t-1$次替换 和 c进行$t-1$次替换之后的长度之和。

定义$f[i][j]$表示字母$j$替换$i$次后的长度（上述举例即为$f[t][0]=f[t-1][1]+f[t-1][2]$），则有：

$$f[i][j]=\sum _{k=1}^{nums[j]}f[i-1][(j+k)\mathrm{mod}26]$$

初始值$f[0][j]=1$，答案为${\sum }_{j=0}^{25}f[t][j]\cdot cnt[j]$，其中$cnt[j]$是$j$出现的次数。

但是直接计算时间复杂度为$O(t\cdot C)$（其中$C=26$），肯定超时。

矩阵快速幂优化

以样例一为例（其实也就是3335. 字符串转换后的长度 I）：$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]$

于是有：

$$\begin{array}{rl}f[i][0]& =f[i-1][1]\\ f[i][1]& =f[i-1][2]\\ f[i][2]& =f[i-1][3]\\ ⋮& \\ f[i][23]& =f[i-1][24]\\ f[i][24]& =f[i-1][25]\\ f[i][25]& =f[i-1][0]+f[i-1][1]\end{array}$$

使用矩阵表示，有：

$$\left[\begin{array}{c}f[i][0]\\ f[i][1]\\ f[i][2]\\ ⋮\\ f[i][23]\\ f[i][24]\\ f[i][25]\end{array}\right]=\left[\begin{array}{ccccccc}0& 1& 0& 0& \cdots & 0& 0\\ 0& 0& 1& 0& \cdots & 0& 0\\ 0& 0& 0& 1& \cdots & 0& 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& 0& \cdots & 1& 0\\ 0& 0& 0& 0& \cdots & 0& 1\\ 1& 1& 0& 0& \cdots & 0& 0\end{array}\right]\left[\begin{array}{c}f[i-1][0]\\ f[i-1][1]\\ f[i-1][2]\\ ⋮\\ f[i-1][23]\\ f[i-1][24]\\ f[i-1][25]\end{array}\right]$$

把上式中的三个矩阵分别记作$F[i],M,F[i-1]$，即

$$F[i]=M\times F[i-1]$$

则有：

$$\begin{array}{rl}F[t]& =M\times F[t-1]\\ & =M\times M\times F[t-2]\\ & =M\times M\times M\times F[t-3]\\ & ⋮\\ & =M^t\times F[0]\end{array}$$

也就是说，我们只需要在$\log t\times C^3$的时间内算出$M^t$，问题就解决了。

使用矩阵快速幂即可完美解决。

听到矩阵快速幂不要怕，它和快速幂的原理是一模一样的，只是把快速幂中的整数乘法换成了矩阵乘法而已。

• 时间复杂度$O(len(s)+C^3\log t)$，其中$C=26$
• 空间复杂度$O(C^2)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-05-14 09:36:25
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-14 23:47:59
 * @Description: AC,40.84%,94.37%
 */
typedef long long ll;
typedef array<array<ll, 26>, 26> Matrix;

class Solution {
private:
    static const int MOD = 1000000007;
    
    Matrix Pow(Matrix a, int b) {
        Matrix ans{};
        for (int i = 0; i < 26; i++) {
            ans[i][i] = 1;
        }
        while (b) {
            if (b & 1) {
                ans = Mul(ans, a);
            }
            a = Mul(a, a);
            b >>= 1;
        }
        return ans;
    }

    Matrix Mul(Matrix& a, Matrix& b) {
        Matrix ans{};
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                for (int k = 0; k < 26; k++) {
                    ans[i][k] = (ans[i][k] + a[i][j] * b[j][k] % MOD) % MOD;
                }
            }
        }
        return ans;
    }
public:
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        Matrix M{};
        for (int i = 0; i < 26; i++) {
            for (int j = 1; j <= nums[i]; j++) {
                M[i][(i + j) % 26] = 1;
            }
        }
        M = Pow(M, t);
        ll cnt[26] = {0};
        for (char c : s) {
            cnt[c - 'a']++;
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                ans = (ans + M[i][j] * cnt[i] % MOD) % MOD;
            }
        }
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-05-14 22:01:41
LastEditors: LetMeFly.xyz
LastEditTime: 2025-05-14 23:46:10
'''
from typing import List

MOD = 1000000007

class Solution:
    def mul(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
        ans = [[0] * 26 for _ in range(26)]
        for i in range(26):
            for k in range(26):
                for j in range(26):
                    ans[i][j] = (ans[i][j] + a[i][k] * b[k][j]) % MOD
        return ans

    def pow(self, a: List[List[int]], b: int) -> List[List[int]]:
        ans = [[0] * 26 for _ in range(26)]
        for i in range(26):
            ans[i][i] = 1
        while b:
            if b & 1:
                ans = self.mul(ans, a)
            a = self.mul(a, a)
            b >>= 1
        return ans
    
    def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
        M = [[0] * 26 for _ in range(26)]
        for i, v in enumerate(nums):
            for j in range(1, v + 1):
                M[i][(i + j) % 26] = 1
        Mt = self.pow(M, t)
        cnt = [0] * 26
        for c in s:
            cnt[ord(c) - ord('a')] += 1
        ans = 0
        for i in range(26):
            ans += sum(Mt[i]) * cnt[i]
        return ans % MOD

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-05-13 09:02:15
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-13 09:19:43
 */

class Solution {
    private final int MOD = 1000000007;

    public int lengthAfterTransformations(String s, int t) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
        }
        int ans = s.length();
        while (t-- > 0) {
            int z = cnt[25];
            for (int i = 24; i >= 0; i--) {
                cnt[i + 1] = cnt[i];
            }
            cnt[0] = z;
            cnt[1] = (cnt[1] + z) % MOD;
            ans = (ans + z) % MOD;
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-05-15 09:49:53
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-15 10:05:13
 */
package main

var MOD3337 = int64(1000000007)

type matrix3337 [26][26]int64

func pow(a matrix3337, b int) (ans matrix3337) {
    for i := 0; i < 26; i++ {
        ans[i][i] = 1
    }
    for ; b > 0; b >>= 1 {
        if b & 1 == 1 {
            ans = mul(ans, a)
        }
        a = mul(a, a)
    }
    return
}

func mul(a, b matrix3337) (ans matrix3337) {
    for i := 0; i < 26; i++ {
        for k := 0; k < 26; k++ {
            for j := 0; j < 26; j++ {
                ans[i][j] = (ans[i][j] + a[i][k] * b[k][j]) % MOD3337
            }
        }
    }
    return
}

func lengthAfterTransformations(s string, t int, nums []int) int {
    M := matrix3337{}
    for i, d := range nums {
        for j := 1; j <= d; j++ {
            M[i][(i + j) % 26] = 1
        }
    }
    Mt := pow(M, t)
    times := make([]int64, 26)
    for i := 0; i < len(s); i++ {
        times[s[i] - 'a']++
    }
    ans := int64(0)
    for i := 0; i < 26; i++ {
        sum := int64(0)
        for j := 0; j < 26; j++ {
            sum += Mt[i][j]
        }
        ans = (ans + sum * times[i]) % MOD3337
    }
    return int(ans)
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源