3335. 字符串转换后的长度 I（Rating 1806）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

3335. 字符串转换后的长度 I

Rating 1806

思路

思路 1（递推）

根据题目描述，答案会非常大，所以模拟肯定是行不通的。

而且本题只需要输出最后的数量，不需要具体的序列，所以也没有必要模拟。

一开始考虑从a出发，判断多少次后会变成2个，再多少次后会变成3个，写了几层发现有一定规律，但非常不好实现，而且很容易出错。因此放弃此思路。

因为题目只有小写字母，因此可以从字母本身出发（这一点貌似在很多题目中都比较好使）

首先统计每个字母出现的次数，在一次变换中按照规则更新这些次数即可，只需要遍历t次，每次遍历26个字母，因此有代码 1

思路 2（矩阵快速幂）

在翻看题解的过程中发现此题还有个加强版 3337. 字符串转换后的长度 II。

思路和本题差不多，但其中t到的数量级变为了10^9，显然是不能通过遍历t来得到答案了。

这里参考了下题解的思路，即

线性递推是可以用矩阵乘法来表示的。

将递推过程写成矩阵乘法后，再结合利用矩阵的快速幂，即可以较低复杂度得到答案。

直接见代码 2。

3337加强版可见代码 3.

代码

代码 1

 class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        MOD = 10**9 + 7
        cnt = [0] * 26
        for c in s:
            cnt[ord(c) - ord('a')] += 1 # 统计每个字母出现次数
        while t: # 按照t次变换
            t -= 1
            tmp = [0] * 26 # 设置一个临时变量记录1次变换后的各个字母次数
            for i in range(25): # a -> y 会变成 b -> z，次数依次传递
                tmp[i + 1] = cnt[i]
            tmp[0] = (tmp[0] + cnt[25]) % MOD # z 既会变成 a
            tmp[1] = (tmp[1] + cnt[25]) % MOD # z 也会变成 b
            for i in range(26):
                cnt[i] = tmp[i] # 更新
        return sum(cnt) % MOD # 答案

代码 2

import numpy as np # 矩阵乘法偷懒使用一下numpy，当然也可以自己实现
class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        def fastMatPow(A, t): # 矩阵快速幂
            ret = np.eye(26, dtype=object)
            base = A
            while t:
                if t % 2:
                    ret = base @ ret % MOD
                base = base @ base % MOD
                t = t // 2
            return ret
        
        MOD = 10**9 + 7
        cnt = np.zeros(26, dtype=object)
        for c in s:
            cnt[ord(c) - ord('a')] += 1 # 统计每个字母出现次数
        mat = np.zeros((26, 26), dtype=object) # 设置递推矩阵
        for i in range(1, 26):
            mat[i][i - 1] = 1 # 字母i是由字母i-1得到的，因此对应位置设为1
        mat[0][25] = 1 # 字母a可以由字母z得到，因此对应位置设为1
        mat[1][25] = 1 # 字母b可以由字母z得到，因此对应位置设为1
        mat = fastMatPow(mat, t) # 递推t次，等价于矩阵求t次幂，使用矩阵快速幂加速
        ret = mat @ cnt # 计算t次变换后各个字母的cnt
        return int(sum(ret)) % MOD # 返回答案

代码 3（加强版对应代码）

import numpy as np
class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        def fastMatPow(A, t):
            ret = np.eye(26, dtype=object)
            base = A
            while t:
                if t & 1:
                    ret = ret @ base % MOD
                base = base @ base % MOD
                t = t >> 1
            return ret

        MOD = 10**9 + 7
        nums = [1] * 26 # 这里对应3337题目加强版的变换设定。注释掉这两行即可过3337
        nums[25] = 2 
        cnt = np.zeros((26, ), dtype=object)
        for c in s:
            cnt[ord(c) - ord('a')] += 1
        mat = np.zeros((26, 26), dtype=object)
        for ind, num in enumerate(nums): # 按照变换设定建立转移矩阵
            for i in range(1, num + 1):
                mat[(ind + i) % 26][ind] = 1
        mat = fastMatPow(mat, t)
        cnt = mat @ cnt
        return sum(cnt) % MOD

细节

这里如果用numpy实现矩阵乘法的话，dtype需要设定为object，不然会爆int