Leetcode 3335. Total Characters in String After Transformations I

Jimmy   May 13, 2025   814 words   ~20 mins
#Hash Table #Math #String #Dynamic Programming #Counting

Table of Contents

題目資訊

題目敘述

你有一個字串 s 和一個整數 t，代表需要執行的轉換次數。在一次轉換中，s 中的每個字元都會根據以下規則進行替換：

  • 如果字元是 'z'，則將其替換為字串 "ab"。
  • 否則，用字母表中的下一個字元替換。例如，'a' 被替換為 'b'，'b' 被替換為 'c'，以此類推。

返回經過恰好 t 次轉換後結果字串的長度。

由於答案可能非常大，返回它對 $10^9 + 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 \leq s.\text{length} \leq 10^5$
  • s 只包含小寫英文字母。
  • $1 \leq t \leq 10^5$

直覺

此問題涉及對字串進行一系列轉換，其中每個字元要麼增加到下一個字母字元，要麼在 ‘z’ 的情況下被替換為較長的字串。挑戰在於在潛在大量轉換（最多至 $10^5$ 次）後有效地確定字串的長度，因為直接模擬會因字串長度的指數增長而在計算上不切實際。

指導我們方法的關鍵觀察是，對於 ‘z’ 以外的任何字元，其轉換路徑是直接的：從一個字元進展到下一個字元。然而，對於 ‘z’，它被替換為兩個字元，即 ‘a’ 和 ‘b’，從而導致總長度的指數級增長。為了有效地計算多次轉換後的長度，我們可以利用線性轉換和矩陣乘冪的性質，將這些字元轉換編碼為一個矩陣，並通過矩陣快速冪次運算來迭代地計算其效果。

解法

為了確定在 t 次轉換後字串的長度，我們採用一種矩陣快速冪次的方法，將字元轉換表示為 26 維空間中的線性轉換（對應於 26 個字母字符）。

  1. 向量和矩陣的表示：

    • 我們使用一個 26 維的向量 characterCount 來表示初始字串 s，其中每個元素對應於某一個特定字元（從 ‘a’ 到 ‘z’）的計數。
    • 定義一個 26x26 的轉換矩陣 M 來編碼轉換規則：
      • 對於從 ‘a’ 到 ‘y’ 的字元，每個字元轉換到下一個字元，因此矩陣 M 將有 M[i][i-1] = 1。
      • 對於 ‘z’，它轉換至 ‘a’ 和 ‘b’，這由設置 M[0][25] = 1 和 M[1][25] = 1 來捕捉。

  2. 矩陣快速冪次：

    • 使用快速矩陣乘冪計算矩陣冪 M^t。這有效地計算應用轉換矩陣 t 次的效果。
    • 此方法利用矩陣乘法的性質，以對數時間相對於 t 計算結果。

  3. 應用轉換：

    • 用矩陣 M^t 乘初始 characterCount 向量，結果為一個新的向量，該向量表示經過轉換後的字元計數。
    • 將此結果向量的元素相加以獲取在 t 次轉換後字串的總長度。

  4. 取模運算：

    • 由於最終長度可能非常大，所有涉及計數的運算均對 $10^9 + 7$ 取模，以防止溢出並滿足問題的限制。

通過利用矩陣快速冪次，此方法可在可接受的時間複雜度內有效地計算出大量轉換後字串的長度，具體為 $O(T \log t)$，其中 $T$ 因字母大小固定為常數。

程式碼

C++

#include <array>
#include <string>

class Solution {
    // 定義大型質數模數
    static constexpr long long MOD = 1'000'000'007;
    // 定義一個具有固定維度26x26的矩陣型別
    using Mat = std::array<std::array<long long, 26>, 26>;
    // 定義一個具有固定維度26的向量型別
    using Vec = std::array<long long, 26>;

    // 將兩個矩陣A和B相乘
    static Mat multiplyMatrix(const Mat& A, const Mat& B) {
        Mat C{};
        for (int i = 0; i < 26; ++i) {
            for (int k = 0; k < 26; ++k) {
                if (A[i][k]) {
                    long long a_ik = A[i][k];
                    for (int j = 0; j < 26; ++j) {
                        C[i][j] += a_ik * B[k][j] % MOD;
                        if (C[i][j] >= MOD) C[i][j] -= MOD;
                    }
                }
            }
        }
        return C;
    }

    // 將矩陣A與向量v相乘
    static Vec multiplyMatrixVector(const Mat& A, const Vec& v) {
        Vec result{};
        for (int i = 0; i < 26; ++i) {
            long long sum = 0;
            for (int j = 0; j < 26; ++j) {
                sum += A[i][j] * v[j] % MOD;
                if (sum >= MOD) sum -= MOD;
            }
            result[i] = sum;
        }
        return result;
    }

    // 使用快速冪計算矩陣的乘方
    static Mat matrixPower(Mat base, int exp) {
        Mat result{}; // 初始化單位矩陣
        for (int i = 0; i < 26; ++i) result[i][i] = 1;

        while (exp) {
            if (exp & 1) result = multiplyMatrix(result, base);
            base = multiplyMatrix(base, base);
            exp >>= 1;
        }
        return result;
    }

public:
    // 計算經過t次轉換後字串的長度
    int lengthAfterTransformations(std::string s, int t) {
        // 步驟1：將初始字串轉換為26維的計數向量
        Vec characterCount{};
        for (char c : s) characterCount[c - 'a']++;

        // 步驟2：為單次轉換創建一個26x26的轉換矩陣M
        Mat M{}; // 初始所有元素為零
        for (int i = 0; i < 25; ++i) // 從x轉換到x+1
            M[i + 1][i] = 1;
        M[0][25] = 1; // 從'z'轉換到'a'
        M[1][25] = 1; // 從'z'轉換到'b'

        // 步驟3：計算矩陣M^t
        Mat Mt = matrixPower(M, t);

        // 步驟4：乘以向量和矩陣來獲得最終的字符計數
        Vec finalCount = multiplyMatrixVector(Mt, characterCount);
        long long finalLength = 0;
        for (long long count : finalCount) {
            finalLength += count;
            if (finalLength >= MOD) finalLength -= MOD;
        }
        return static_cast<int>(finalLength);
    }
};

Python

class Solution:
    # 定義一個大的質數模數
    MOD = 1_000_000_007
    # 定義一個固定維度為26x26的矩陣類型
    Mat = list[list[int]]
    # 定義一個固定維度為26的向量類型
    Vec = list[int]

    # 矩陣A與矩陣B的乘法
    @staticmethod
    def multiplyMatrix(A: 'Solution.Mat', B: 'Solution.Mat') -> 'Solution.Mat':
        C = [[0] * 26 for _ in range(26)]
        for i in range(26):
            for k in range(26):
                if A[i][k]:
                    a_ik = A[i][k]
                    for j in range(26):
                        C[i][j] += a_ik * B[k][j] % Solution.MOD
                        if C[i][j] >= Solution.MOD:
                            C[i][j] -= Solution.MOD
        return C

    # 矩陣A與向量v的乘法
    @staticmethod
    def multiplyMatrixVector(A: 'Solution.Mat', v: 'Solution.Vec') -> 'Solution.Vec':
        result = [0] * 26
        for i in range(26):
            sum = 0
            for j in range(26):
                sum += A[i][j] * v[j] % Solution.MOD
                if sum >= Solution.MOD:
                    sum -= Solution.MOD
            result[i] = sum
        return result

    # 使用快速冪次法計算矩陣的冪次
    @staticmethod
    def matrixPower(base: 'Solution.Mat', exp: int) -> 'Solution.Mat':
        result = [[0] * 26 for _ in range(26)]  # 初始化單位矩陣
        for i in range(26):
            result[i][i] = 1

        while exp:
            if exp & 1:
                result = Solution.multiplyMatrix(result, base)
            base = Solution.multiplyMatrix(base, base)
            exp >>= 1
        return result

    # 計算經過t次變換後字串的長度
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        # 步驟1：將初始字串轉換為26維的計數向量
        characterCount = [0] * 26
        for c in s:
            characterCount[ord(c) - ord('a')] += 1

        # 步驟2：為一次變換創建一個26x26的轉換矩陣M
        M = [[0] * 26 for _ in range(26)] # 初始所有元素皆為零
        for i in range(25): # 從x轉換到x+1
            M[i + 1][i] = 1
        M[0][25] = 1 # 從'z'轉換到'a'
        M[1][25] = 1 # 從'z'轉換到'b'

        # 步驟3：計算矩陣M的t次方
        Mt = Solution.matrixPower(M, t)

        # 步驟4：將向量與矩陣相乘以獲得最終的字符計數
        finalCount = Solution.multiplyMatrixVector(Mt, characterCount)
        finalLength = 0
        for count in finalCount:
            finalLength += count
            if finalLength >= Solution.MOD:
                finalLength -= Solution.MOD
        return finalLength

複雜度分析

  • 時間複雜度: $O(26^3 \cdot \log{t})$

    時間複雜度主要由矩陣冪運算過程所主導，該過程涉及矩陣乘法。由於矩陣的大小固定為 $26 \times 26$，矩陣乘法的複雜度為常數 $O(26^3)$。矩陣冪運算使用快速冪次法（或平方乘法）實現，需要 $O(\log{t})$ 步驟。因此，總時間複雜度為 $O(26^3 \cdot \log{t})$，考慮到矩陣的固定維度，這實際上是一個常數時間操作。

  • 空間複雜度: $O(1)$

    空間複雜度為 $O(1)$，因為矩陣和向量使用的空間不會隨輸入大小或變換次數 $t$ 增加。矩陣和向量的維度是常數，因為它們表示的是固定的26個字母字符集，導致空間使用量不變。因此，空間複雜度保持常數。

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.