3337. 字符串变换后的总字符数 II

Hard

题目描述

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

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

提示：

1 <= s.length <= 10^5
s 仅由小写英文字母组成
1 <= t <= 10^9
nums.length == 26
1 <= nums[i] <= 25

解题思路

这道题是一个典型的矩阵快速幂问题。关键观察是每次变换都可以表示为一个线性变换，可以用矩阵乘法来表示。

核心思路：

状态表示：用一个长度为 26 的向量表示当前 26 个字母的数量
变换矩阵：构造一个 26×26 的矩阵 M，其中 M[i][j] 表示字母 i 变换后对字母 j 的贡献
矩阵构造：对于字母 i，它会变成 nums[i] 个连续字母，从 (i+1) % 26 开始
快速幂优化：由于 t 可能很大（10^9），需要用矩阵快速幂来计算 M^t

算法步骤：

统计初始字符串中每个字母的数量
构造变换矩阵：M[i][(i+j+1)%26] = 1，其中 j ∈ [0, nums[i]-1]
使用矩阵快速幂计算 M^t
将初始状态向量与 M^t 相乘得到最终状态
求和得到总字符数

时间复杂度主要在矩阵快速幂的计算上，每次矩阵乘法是 O(26^3)，快速幂需要 O(log t) 次。

代码实现

class Solution {
public:
    static const int MOD = 1000000007;
    
    vector<vector<long long>> multiply(const vector<vector<long long>>& A, const vector<vector<long long>>& B) {
        int n = A.size();
        vector<vector<long long>> C(n, vector<long long>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
                }
            }
        }
        return C;
    }
    
    vector<vector<long long>> matrixPower(vector<vector<long long>>& mat, int t) {
        int n = mat.size();
        vector<vector<long long>> result(n, vector<long long>(n, 0));
        for (int i = 0; i < n; i++) {
            result[i][i] = 1;
        }
        
        while (t > 0) {
            if (t & 1) {
                result = multiply(result, mat);
            }
            mat = multiply(mat, mat);
            t >>= 1;
        }
        return result;
    }
    
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        vector<long long> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        
        vector<vector<long long>> mat(26, vector<long long>(26, 0));
        for (int i = 0; i < 26; i++) {
            for (int j = 1; j <= nums[i]; j++) {
                mat[i][(i + j) % 26]++;
            }
        }
        
        vector<vector<long long>> powered = matrixPower(mat, t);
        
        vector<long long> result(26, 0);
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                result[i] = (result[i] + count[j] * powered[j][i]) % MOD;
            }
        }
        
        long long total = 0;
        for (int i = 0; i < 26; i++) {
            total = (total + result[i]) % MOD;
        }
        return total;
    }
};

class Solution:
    def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
        MOD = 10**9 + 7
        
        def multiply(A, B):
            n = len(A)
            C = [[0] * n for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    for k in range(n):
                        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
            return C
        
        def matrix_power(mat, t):
            n = len(mat)
            result = [[0] * n for _ in range(n)]
            for i in range(n):
                result[i][i] = 1
            
            while t > 0:
                if t & 1:
                    result = multiply(result, mat)
                mat = multiply(mat, mat)
                t >>= 1
            return result
        
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        
        mat = [[0] * 26 for _ in range(26)]
        for i in range(26):
            for j in range(1, nums[i] + 1):
                mat[i][(i + j) % 26] += 1
        
        powered = matrix_power(mat, t)
        
        result = [0] * 26
        for i in range(26):
            for j in range(26):
                result[i] = (result[i] + count[j] * powered[j][i]) % MOD
        
        return sum(result) % MOD

public class Solution {
    private const int MOD = 1000000007;
    
    private long[,] Multiply(long[,] A, long[,] B) {
        int n = A.GetLength(0);
        long[,] C = new long[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    C[i, j] = (C[i, j] + A[i, k] * B[k, j]) % MOD;
                }
            }
        }
        return C;
    }
    
    private long[,] MatrixPower(long[,] mat, int t) {
        int n = mat.GetLength(0);
        long[,] result = new long[n, n];
        for (int i = 0; i < n; i++) {
            result[i, i] = 1;
        }
        
        while (t > 0) {
            if ((t & 1) == 1) {
                result = Multiply(result, mat);
            }
            mat = Multiply(mat, mat);
            t >>= 1;
        }
        return result;
    }
    
    public int LengthAfterTransformations(string s, int t, IList<int> nums) {
        long[] count = new long[26];
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        long[,] mat = new long[26, 26];
        for (int i = 0; i < 26; i++) {
            for (int j = 1; j <= nums[i]; j++) {
                mat[i, (i + j) % 26]++;
            }
        }
        
        long[,] powered = MatrixPower(mat, t);
        
        long[] result = new long[26];
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                result[i] = (result[i] + count[j] * powered[j, i]) % MOD;
            }
        }
        
        long total = 0;
        for (int i = 0; i < 26; i++) {
            total = (total + result[i]) % MOD;
        }
        return (int)total;
    }
}

var lengthAfterTransformations = function(s, t, nums) {
    const MOD = 1000000007;
    
    function multiply(A, B) {
        const n = A.length;
        const C = Array(n).fill().map(() => Array(n).fill(0));
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                for (let k = 0; k < n; k++) {
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
                }
            }
        }
        return C;
    }
    
    function matrixPower(mat, t) {
        const n = mat.length;
        let result = Array(n).fill().map(() => Array(n).fill(0));
        for (let i = 0; i < n; i++) {
            result[i][i] = 1;
        }
        
        while (t > 0) {
            if (t & 1) {
                result = multiply(result, mat);
            }
            mat = multiply(mat, mat);
            t >>= 1;
        }
        return result;
    }
    
    const count = Array(26).fill(0);
    for (let c of s) {
        count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    const mat = Array(26).fill().map(() => Array(26).fill(0));
    for (let i = 0; i < 26; i++) {
        for (let j = 1; j <= nums[i]; j++) {
            mat[i][(i + j) % 26]++;
        }
    }
    
    const powered = matrixPower(mat, t);
    
    const result = Array(26).fill(0);
    for (let i = 0; i < 26; i++) {
        for (let j = 0; j < 26; j++) {
            result[i] = (result[i] + count[j] * powered[j][i]) % MOD;
        }
    }
    
    return result.reduce((sum, val) => (sum + val) % MOD, 0);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度
时间复杂度	O(26³ × log t)
空间复杂度	O(26²)

说明：

时间复杂度：矩阵快速幂需要 O(log t) 次矩阵乘法，每次乘法是 O(26³)
空间复杂度：需要存储 26×26 的变换矩阵

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析