class Solution {
public:
int lengthAfterTransformations(string s, int t) {
}
};
3335. 字符串转换后的长度 I
给你一个字符串 s 和一个整数 t，表示要执行的 转换 次数。每次 转换 需要根据以下规则替换字符串 s 中的每个字符：
'z'，则将其替换为字符串 "ab"。'a' 替换为 'b'，'b' 替换为 'c'，依此类推。返回 恰好 执行 t 次转换后得到的字符串的 长度。
由于答案可能非常大，返回其对 109 + 7 取余的结果。
示例 1：
输入： s = "abcyy", t = 2
输出： 7
解释：
'a' 变为 'b''b' 变为 'c''c' 变为 'd''y' 变为 'z''y' 变为 'z'"bcdzz"'b' 变为 'c''c' 变为 'd''d' 变为 'e''z' 变为 "ab"'z' 变为 "ab""cdeabab""cdeabab"，长度为 7 个字符。示例 2：
输入： s = "azbk", t = 1
输出： 5
解释：
'a' 变为 'b''z' 变为 "ab"'b' 变为 'c''k' 变为 'l'"babcl""babcl"，长度为 5 个字符。
提示：
1 <= s.length <= 105s 仅由小写英文字母组成。1 <= t <= 105原站题解
java 解法, 执行用时: 117 ms, 内存消耗: 44.4 MB, 提交时间: 2024-11-05 10:41:34
class Solution {
private static final int MOD = 1_000_000_007;
private static final int SIZE = 26;
public int lengthAfterTransformations(String s, int t) {
int[][] f0 = new int[SIZE][1];
List<Integer> nums = Arrays.asList(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);
for (int i = 0; i < SIZE; i++) {
f0[i][0] = 1;
}
int[][] m = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
int c = nums.get(i);
for (int j = i + 1; j <= i + c; j++) {
m[i][j % SIZE] = 1;
}
}
m = powMul(m, t, f0);
int[] cnt = new int[SIZE];
for (char c : s.toCharArray()) {
cnt[c - 'a']++;
}
long ans = 0;
for (int i = 0; i < SIZE; i++) {
ans += (long) m[i][0] * cnt[i];
}
return (int) (ans % MOD);
}
// a^n * f0
private int[][] powMul(int[][] a, int n, int[][] f0) {
int[][] res = f0;
while (n > 0) {
if ((n & 1) > 0) {
res = mul(a, res);
}
a = mul(a, a);
n >>= 1;
}
return res;
}
// 返回矩阵 a 和矩阵 b 相乘的结果
private int[][] mul(int[][] a, int[][] b) {
int[][] c = new int[a.length][b[0].length];
for (int i = 0; i < a.length; i++) {
for (int k = 0; k < a[i].length; k++) {
if (a[i][k] == 0) {
continue;
}
for (int j = 0; j < b[k].length; j++) {
c[i][j] = (int) ((c[i][j] + (long) a[i][k] * b[k][j]) % MOD);
}
}
}
return c;
}
}
golang 解法, 执行用时: 61 ms, 内存消耗: 9.2 MB, 提交时间: 2024-11-05 10:38:10
const mod = 1_000_000_007
type matrix [][]int
func newMatrix(n, m int) matrix {
a := make(matrix, n)
for i := range a {
a[i] = make([]int, m)
}
return a
}
func (a matrix) mul(b matrix) matrix {
c := newMatrix(len(a), len(b[0]))
for i, row := range a {
for k, x := range row {
if x == 0 {
continue
}
for j, y := range b[k] {
c[i][j] = (c[i][j] + x*y) % mod
}
}
}
return c
}
// a^n * f0
func (a matrix) powMul(n int, f0 matrix) matrix {
res := f0
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = a.mul(res)
}
a = a.mul(a)
}
return res
}
func lengthAfterTransformations(s string, t int) (ans int) {
const size = 26
nums := []int{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}
f0 := newMatrix(size, 1)
for i := range f0 {
f0[i][0] = 1
}
m := newMatrix(size, size)
for i, c := range nums {
for j := i + 1; j <= i+c; j++ {
m[i][j%size] = 1
}
}
m = m.powMul(t, f0)
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
for i, row := range m {
ans += row[0] * cnt[i]
}
return ans % mod
}
python3 解法, 执行用时: 1689 ms, 内存消耗: 28.7 MB, 提交时间: 2024-11-05 10:37:07
import numpy as np
MOD = 1_000_000_007
# a^n @ f0
def pow(a: np.ndarray, n: int, f0: np.ndarray) -> np.ndarray:
res = f0
while n:
if n & 1:
res = a @ res % MOD
a = a @ a % MOD
n >>= 1
return res
class Solution:
def lengthAfterTransformations(self, s: str, t: int) -> int:
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]
SIZE = 26
f0 = np.ones((SIZE,), dtype=object)
m = np.zeros((SIZE, SIZE), dtype=object)
for i, c in enumerate(nums):
for j in range(i + 1, i + c + 1):
m[i, j % SIZE] = 1
m = pow(m, t, f0)
ans = 0
for ch, cnt in Counter(s).items():
ans += m[ord(ch) - ord('a')] * cnt
return ans % MOD