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

题目描述

给你一个字符串 s 和一个整数 t，表示要执行的转换次数。每次转换需要根据以下规则替换字符串 s 中的每个字符：

如果字符是 'z'，则将其替换为字符串 "ab"。
否则，将其替换为字母表中的下一个字符。例如，'a' 替换为 'b'，'b' 替换为 'c'，依此类推。

返回恰好执行 t 次转换后得到的字符串的长度。

由于答案可能非常大，返回其对 10⁹ + 7 取余的结果。

示例 1：

输入： s = "abcyy", t = 2

输出： 7

解释：

第一次转换 (t = 1)
- 'a' 变为 'b'
- 'b' 变为 'c'
- 'c' 变为 'd'
- 'y' 变为 'z'
- 'y' 变为 'z'
- 第一次转换后的字符串为："bcdzz"
第二次转换 (t = 2)
- 'b' 变为 'c'
- 'c' 变为 'd'
- 'd' 变为 'e'
- 'z' 变为 "ab"
- 'z' 变为 "ab"
- 第二次转换后的字符串为："cdeabab"
最终字符串长度：字符串为 "cdeabab"，长度为 7 个字符。

示例 2：

输入： s = "azbk", t = 1

输出： 5

解释：

第一次转换 (t = 1)
- 'a' 变为 'b'
- 'z' 变为 "ab"
- 'b' 变为 'c'
- 'k' 变为 'l'
- 第一次转换后的字符串为："babcl"
最终字符串长度：字符串为 "babcl"，长度为 5 个字符。

提示：

1 <= s.length <= 10⁵
s 仅由小写英文字母组成。
1 <= t <= 10⁵

解法

方法一：递推

我们定义 \(f[i][j]\) 表示经过 \(i\) 次转换后，字母表中第 \(j\) 个字母的个数。初始时 \(f[0][j]\) 为字符串 \(s\) 中字母表中第 \(j\) 个字母的个数。

每次转换后，字母表中第 \(j\) 个字母的个数可以通过以下方式计算：

\[ \begin{align*} f[i][0] &= f[i - 1][25] \\ f[i][1] &= f[i - 1][0] + f[i - 1][25] \\ f[i][2] &= f[i - 1][1] \\ f[i][3] &= f[i - 1][2] \\ &\vdots \\ f[i][25] &= f[i - 1][24] \end{align*} \]

答案为 \(f[t][0] + f[t][1] + \ldots + f[t][25]\)。

由于答案可能非常大，我们需要对 \(10^9 + 7\) 取模。

Python3JavaC++GoTypeScript

class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        f = [[0] * 26 for _ in range(t + 1)]
        for c in s:
            f[0][ord(c) - ord("a")] += 1
        for i in range(1, t + 1):
            f[i][0] = f[i - 1][25]
            f[i][1] = f[i - 1][0] + f[i - 1][25]
            for j in range(2, 26):
                f[i][j] = f[i - 1][j - 1]
        mod = 10**9 + 7
        return sum(f[t]) % mod

class Solution {
    public int lengthAfterTransformations(String s, int t) {
        final int mod = (int) 1e9 + 7;
        int[][] f = new int[t + 1][26];
        for (char c : s.toCharArray()) {
            f[0][c - 'a']++;
        }
        for (int i = 1; i <= t; ++i) {
            f[i][0] = f[i - 1][25] % mod;
            f[i][1] = (f[i - 1][0] + f[i - 1][25]) % mod;
            for (int j = 2; j < 26; j++) {
                f[i][j] = f[i - 1][j - 1] % mod;
            }
        }

        int ans = 0;
        for (int j = 0; j < 26; ++j) {
            ans = (ans + f[t][j]) % mod;
        }
        return ans;
    }
}

class Solution {
public:
    int lengthAfterTransformations(string s, int t) {
        const int mod = 1e9 + 7;
        vector<vector<int>> f(t + 1, vector<int>(26, 0));

        for (char c : s) {
            f[0][c - 'a']++;
        }

        for (int i = 1; i <= t; ++i) {
            f[i][0] = f[i - 1][25] % mod;
            f[i][1] = (f[i - 1][0] + f[i - 1][25]) % mod;
            for (int j = 2; j < 26; ++j) {
                f[i][j] = f[i - 1][j - 1] % mod;
            }
        }

        int ans = 0;
        for (int j = 0; j < 26; ++j) {
            ans = (ans + f[t][j]) % mod;
        }

        return ans;
    }
};

func lengthAfterTransformations(s string, t int) int {
    const mod = 1_000_000_007
    f := make([][]int, t+1)
    for i := range f {
        f[i] = make([]int, 26)
    }

    for _, c := range s {
        f[0][c-'a']++
    }

    for i := 1; i <= t; i++ {
        f[i][0] = f[i-1][25] % mod
        f[i][1] = (f[i-1][0] + f[i-1][25]) % mod
        for j := 2; j < 26; j++ {
            f[i][j] = f[i-1][j-1] % mod
        }
    }

    ans := 0
    for j := 0; j < 26; j++ {
        ans = (ans + f[t][j]) % mod
    }
    return ans
}

function lengthAfterTransformations(s: string, t: number): number {
    const mod = 1_000_000_007;
    const f: number[][] = Array.from({ length: t + 1 }, () => Array(26).fill(0));

    for (const c of s) {
        f[0][c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    for (let i = 1; i <= t; i++) {
        f[i][0] = f[i - 1][25] % mod;
        f[i][1] = (f[i - 1][0] + f[i - 1][25]) % mod;
        for (let j = 2; j < 26; j++) {
            f[i][j] = f[i - 1][j - 1] % mod;
        }
    }

    let ans = 0;
    for (let j = 0; j < 26; j++) {
        ans = (ans + f[t][j]) % mod;
    }

    return ans;
}

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

题目描述

解法

方法一：递推

评论