LeetCode 题解工作台
字符串转换后的长度 II
给你一个由小写英文字母组成的字符串 s ，一个整数 t 表示要执行的 转换 次数，以及一个长度为 26 的数组 nums 。每次 转换 需要根据以下规则替换字符串 s 中的每个字符： 将 s[i] 替换为字母表中后续的 nums[s[i] - 'a'] 个连续字符。例如，如果 s[i] = 'a' …
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们定义 表示经过 次转换后，字母表中第 个字母的个数。初始时 为字符串 中字母表中第 个字母的个数。 由于每一次转换后第 个字母的个数，都跟下一次转换有关，转换的次数 较大，我们可以使用矩阵快速幂，来加速整个递推过程。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个由小写英文字母组成的字符串 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)
'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 <= 105s仅由小写英文字母组成。1 <= t <= 109nums.length == 261 <= nums[i] <= 25
解题思路
方法一：矩阵快速幂加速递推
我们定义 表示经过 次转换后，字母表中第 个字母的个数。初始时 为字符串 中字母表中第 个字母的个数。
由于每一次转换后第 个字母的个数，都跟下一次转换有关，转换的次数 较大，我们可以使用矩阵快速幂，来加速整个递推过程。
注意，答案可能非常大，我们需要对 取模。
时间复杂度 ，空间复杂度 。其中 为字母表的大小。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + log t * |Σ|^3) due to matrix exponentiation on a 26x26 matrix, and space complexity is O(|Σ|^2) for storing the transformation matrix. |
| 空间 | O( |
面试官常问的追问
外企场景- question_mark
Recognize the problem as state transition dynamic programming suitable for matrix modeling.
- question_mark
Identify that direct simulation will fail for large t due to exponential growth.
- question_mark
Look for modular arithmetic to handle large numeric results.
常见陷阱
外企场景- error
Trying to simulate all transformations directly, leading to TLE.
- error
Incorrectly building the transformation matrix, mixing row and column meanings.
- error
Forgetting to apply modulo at each multiplication step, causing overflow.
进阶变体
外企场景- arrow_right_alt
Compute the length of the string after transformations but return the full expanded string instead.
- arrow_right_alt
Transformations vary per character type with different nums arrays per step.
- arrow_right_alt
Consider transformations on multibyte characters or extended alphabets instead of just lowercase letters.