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 次转换后得到的字符串的 长度。
由于答案可能非常大，返回其对 109 + 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)
<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：
输入： 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)
<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 <= 105s仅由小写英文字母组成。1 <= t <= 109nums.length == 261 <= nums[i] <= 25
解法
方法一：矩阵快速幂加速递推
我们定义 $f[i][j]$ 表示经过 $i$ 次转换后，字母表中第 $j$ 个字母的个数。初始时 $f[0][j]$ 为字符串 $s$ 中字母表中第 $j$ 个字母的个数。
由于每一次转换后第 $j$ 个字母的个数，都跟下一次转换有关，转换的次数 $t$ 较大，我们可以使用矩阵快速幂，来加速整个递推过程。
注意，答案可能非常大，我们需要对 $10^9 + 7$ 取模。
时间复杂度 $O(n + \log t \times |\Sigma|^3)$，空间复杂度 $O(|\Sigma|^2)$。其中 $|\Sigma|$ 为字母表的大小。
Python3
class Solution:
def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
mod = 10**9 + 7
m = 26
cnt = [0] * m
for c in s:
cnt[ord(c) - ord("a")] += 1
matrix = [[0] * m for _ in range(m)]
for i, x in enumerate(nums):
for j in range(1, x + 1):
matrix[i][(i + j) % m] = 1
def matmul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
n, p, q = len(a), len(b), len(b[0])
res = [[0] * q for _ in range(n)]
for i in range(n):
for k in range(p):
if a[i][k]:
for j in range(q):
res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod
return res
def matpow(mat: List[List[int]], power: int) -> List[List[int]]:
res = [[int(i == j) for j in range(m)] for i in range(m)]
while power:
if power % 2:
res = matmul(res, mat)
mat = matmul(mat, mat)
power //= 2
return res
cnt = [cnt]
factor = matpow(matrix, t)
result = matmul(cnt, factor)[0]
ans = sum(result) % mod
return ans
Java
class Solution {
private final int mod = (int) 1e9 + 7;
public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
final int m = 26;
int[] cnt = new int[m];
for (char c : s.toCharArray()) {
cnt[c - 'a']++;
}
int[][] matrix = new int[m][m];
for (int i = 0; i < m; i++) {
int num = nums.get(i);
for (int j = 1; j <= num; j++) {
matrix[i][(i + j) % m] = 1;
}
}
int[][] factor = matpow(matrix, t, m);
int[] result = vectorMatrixMultiply(cnt, factor);
int ans = 0;
for (int val : result) {
ans = (ans + val) % mod;
}
return ans;
}
private int[][] matmul(int[][] a, int[][] b) {
int n = a.length;
int p = b.length;
int q = b[0].length;
int[][] res = new int[n][q];
for (int i = 0; i < n; i++) {
for (int k = 0; k < p; k++) {
if (a[i][k] == 0) continue;
for (int j = 0; j < q; j++) {
res[i][j] = (int) ((res[i][j] + 1L * a[i][k] * b[k][j]) % mod);
}
}
}
return res;
}
private int[][] matpow(int[][] mat, int power, int m) {
int[][] res = new int[m][m];
for (int i = 0; i < m; i++) {
res[i][i] = 1;
}
while (power > 0) {
if ((power & 1) != 0) {
res = matmul(res, mat);
}
mat = matmul(mat, mat);
power >>= 1;
}
return res;
}
private int[] vectorMatrixMultiply(int[] vector, int[][] matrix) {
int n = matrix.length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
long sum = 0;
for (int j = 0; j < n; j++) {
sum = (sum + 1L * vector[j] * matrix[j][i]) % mod;
}
result[i] = (int) sum;
}
return result;
}
}
C++
class Solution {
public:
static constexpr int MOD = 1e9 + 7;
static constexpr int M = 26;
using Matrix = vector<vector<int>>;
Matrix matmul(const Matrix& a, const Matrix& b) {
int n = a.size(), p = b.size(), q = b[0].size();
Matrix res(n, vector<int>(q, 0));
for (int i = 0; i < n; ++i) {
for (int k = 0; k < p; ++k) {
if (a[i][k]) {
for (int j = 0; j < q; ++j) {
res[i][j] = (res[i][j] + 1LL * a[i][k] * b[k][j] % MOD) % MOD;
}
}
}
}
return res;
}
Matrix matpow(Matrix mat, int power) {
Matrix res(M, vector<int>(M, 0));
for (int i = 0; i < M; ++i) res[i][i] = 1;
while (power) {
if (power % 2) res = matmul(res, mat);
mat = matmul(mat, mat);
power /= 2;
}
return res;
}
int lengthAfterTransformations(string s, int t, vector<int>& nums) {
vector<int> cnt(M, 0);
for (char c : s) {
cnt[c - 'a']++;
}
Matrix matrix(M, vector<int>(M, 0));
for (int i = 0; i < M; ++i) {
for (int j = 1; j <= nums[i]; ++j) {
matrix[i][(i + j) % M] = 1;
}
}
Matrix cntMat(1, vector<int>(M));
for (int i = 0; i < M; ++i) cntMat[0][i] = cnt[i];
Matrix factor = matpow(matrix, t);
Matrix result = matmul(cntMat, factor);
int ans = 0;
for (int x : result[0]) {
ans = (ans + x) % MOD;
}
return ans;
}
};
Go
func lengthAfterTransformations(s string, t int, nums []int) int {
const MOD = 1e9 + 7
const M = 26
cnt := make([]int, M)
for _, c := range s {
cnt[int(c-'a')]++
}
matrix := make([][]int, M)
for i := 0; i < M; i++ {
matrix[i] = make([]int, M)
for j := 1; j <= nums[i]; j++ {
matrix[i][(i+j)%M] = 1
}
}
matmul := func(a, b [][]int) [][]int {
n, p, q := len(a), len(b), len(b[0])
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, q)
for k := 0; k < p; k++ {
if a[i][k] != 0 {
for j := 0; j < q; j++ {
res[i][j] = (res[i][j] + a[i][k]*b[k][j]%MOD) % MOD
}
}
}
}
return res
}
matpow := func(mat [][]int, power int) [][]int {
res := make([][]int, M)
for i := 0; i < M; i++ {
res[i] = make([]int, M)
res[i][i] = 1
}
for power > 0 {
if power%2 == 1 {
res = matmul(res, mat)
}
mat = matmul(mat, mat)
power /= 2
}
return res
}
cntMat := [][]int{make([]int, M)}
copy(cntMat[0], cnt)
factor := matpow(matrix, t)
result := matmul(cntMat, factor)
ans := 0
for _, v := range result[0] {
ans = (ans + v) % MOD
}
return ans
}
TypeScript
function lengthAfterTransformations(s: string, t: number, nums: number[]): number {
const MOD = BigInt(1e9 + 7);
const M = 26;
const cnt: number[] = Array(M).fill(0);
for (const c of s) {
cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
const matrix: number[][] = Array.from({ length: M }, () => Array(M).fill(0));
for (let i = 0; i < M; i++) {
for (let j = 1; j <= nums[i]; j++) {
matrix[i][(i + j) % M] = 1;
}
}
const matmul = (a: number[][], b: number[][]): number[][] => {
const n = a.length,
p = b.length,
q = b[0].length;
const res: number[][] = Array.from({ length: n }, () => Array(q).fill(0));
for (let i = 0; i < n; i++) {
for (let k = 0; k < p; k++) {
const aik = BigInt(a[i][k]);
if (aik !== BigInt(0)) {
for (let j = 0; j < q; j++) {
const product = aik * BigInt(b[k][j]);
const sum = BigInt(res[i][j]) + product;
res[i][j] = Number(sum % MOD);
}
}
}
}
return res;
};
const matpow = (mat: number[][], power: number): number[][] => {
let res: number[][] = Array.from({ length: M }, (_, i) =>
Array.from({ length: M }, (_, j) => (i === j ? 1 : 0)),
);
while (power > 0) {
if (power % 2 === 1) res = matmul(res, mat);
mat = matmul(mat, mat);
power = Math.floor(power / 2);
}
return res;
};
const cntMat: number[][] = [cnt.slice()];
const factor = matpow(matrix, t);
const result = matmul(cntMat, factor);
let ans = 0n;
for (const v of result[0]) {
ans = (ans + BigInt(v)) % MOD;
}
return Number(ans);
}