class Solution {
public:
int lengthAfterTransformations(string s, int t, vector<int>& nums) {
}
};
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)
'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原站题解
python3 解法, 执行用时: 769 ms, 内存消耗: 29 MB, 提交时间: 2024-11-05 10:35:16
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, nums: List[int]) -> int:
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
python3 解法, 执行用时: 2437 ms, 内存消耗: 17.4 MB, 提交时间: 2024-11-05 10:35:02
MOD = 1_000_000_007
# a @ b，其中 @ 是矩阵乘法
def mul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in zip(*b)]
for row in a]
# a^n @ f0
def pow_mul(a: List[List[int]], n: int, f0: List[List[int]]) -> List[List[int]]:
res = f0
while n:
if n & 1:
res = mul(a, res)
a = mul(a, a)
n >>= 1
return res
class Solution:
def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
SIZE = 26
f0 = [[1] for _ in range(SIZE)]
m = [[0] * SIZE for _ in range(SIZE)]
for i, c in enumerate(nums):
for j in range(i + 1, i + c + 1):
m[i][j % SIZE] = 1
m = pow_mul(m, t, f0)
ans = 0
for ch, cnt in Counter(s).items():
ans += m[ord(ch) - ord('a')][0] * cnt
return ans % MOD
cpp 解法, 执行用时: 67 ms, 内存消耗: 23.6 MB, 提交时间: 2024-11-05 10:34:43
class Solution {
static constexpr int MOD = 1'000'000'007;
static constexpr int SIZE = 26;
using Matrix = array<array<int, SIZE>, SIZE>;
// 返回矩阵 a 和矩阵 b 相乘的结果
Matrix mul(Matrix& a, Matrix& b) {
Matrix c{};
for (int i = 0; i < SIZE; i++) {
for (int k = 0; k < SIZE; k++) {
if (a[i][k] == 0) {
continue;
}
for (int j = 0; j < SIZE; j++) {
c[i][j] = (c[i][j] + (long long) a[i][k] * b[k][j]) % MOD;
}
}
}
return c;
}
// 返回 n 个矩阵 a 相乘的结果
Matrix pow(Matrix a, int n) {
Matrix res = {};
for (int i = 0; i < SIZE; i++) {
res[i][i] = 1; // 单位矩阵
}
while (n) {
if (n & 1) {
res = mul(res, a);
}
a = mul(a, a);
n >>= 1;
}
return res;
}
public:
int lengthAfterTransformations(string s, int t, vector<int>& nums) {
Matrix m{};
for (int i = 0; i < SIZE; i++) {
for (int j = i + 1; j <= i + nums[i]; j++) {
m[i][j % SIZE] = 1;
}
}
m = pow(m, t);
int cnt[SIZE]{};
for (char c : s) {
cnt[c - 'a']++;
}
long long ans = 0;
for (int i = 0; i < SIZE; i++) {
// m 第 i 行的和就是 f[t][i]
ans += reduce(m[i].begin(), m[i].end(), 0LL) * cnt[i];
}
return ans % MOD;
}
};
java 解法, 执行用时: 90 ms, 内存消耗: 44.3 MB, 提交时间: 2024-11-05 10:34:20
class Solution {
private static final int MOD = 1_000_000_007;
private static final int SIZE = 26;
public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
int[][] f0 = new int[SIZE][1];
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 解法, 执行用时: 46 ms, 内存消耗: 8.2 MB, 提交时间: 2024-11-05 10:30:56
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, nums []int) (ans int) {
const size = 26
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
}