題目資訊

題目編號: 1079
題目連結: Letter Tile Possibilities
主題: Hash Table, String, Backtracking, Counting

題目敘述

你有 n 個 瓷磚，其中每個瓷磚上都印有一個字母 tiles[i]。

返回可以使用這些瓷磚上印刷的字母製作的可能非空字母序列的數量。

範例 1:

輸入: tiles = “AAB”
輸出: 8
解釋: 可能的序列是 “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”。

範例 2:

輸入: tiles = “AAABBC”
輸出: 188

範例 3:

輸入: tiles = “V”
輸出: 1

約束條件:

$1 \leq \text{tiles.length} \leq 7$
tiles 由大寫英文字母組成。

直覺

此問題看似簡單，要求從給定的磚塊生成所有可能的非空字母序列。直觀的想法是針對每個磚塊，探索以該磚塊為起始的可能序列。由於磚塊字串的長度限制相對較小（最大長度為7），回溯方法可以有效列舉所有可能的組合，並考慮字元的重複性。

解法

該解法使用回溯機制來探索由磚塊組成的所有潛在序列。主要步驟如下：

頻率計數：演算法首先計算輸入字串 tiles 中每個字母的頻率。這個計數維持在一個大小為26的頻率陣列中，對應於26個大寫英文字母。這使我們能夠在生成序列時高效地檢查每個磚塊的可用性。
回溯函數：一個遞迴函數 backtrack 用來構造可能的序列。該函數操作於決策制定的原則下：在每一步，做出是否將特定字母包括在當前序列中的決定。
- 遞迴與回溯：對於每個可能的字母，如果該字母至少還有一個磚塊可用（頻率大於零），演算法就將其包含在序列中並減少其頻率。然後通過再次調用 backtrack 遞迴探索更長的序列。在遞迴返回後，頻率被增回，即 “撤銷” 了這一個決定，從而探索不包含該字母的替代序列。
- 序列計數：每次函數完成對某個特定序列位置所有潛在起始字母的迭代後，它會增大全域計數器 ans 以計算一個有效序列。
結果計算：從最初狀態開始啟動回溯過程，此時未選擇任何磚塊（空序列），頻率圖反映了輸入中每個磚塊的計數。最後，累積所有非空序列數量的計數器 ans 被返回。

此方法透過回溯技術有效生成所有可能的非空字母序列，自然考慮了字母的排列與組合，包括當字母多次出現時的重複序列。

程式碼

C++

class Solution {
public:
    // 初始化可能序列的計數器
    int ans = -1;

    // 回溯函數以探索所有可能的序列
    void backtrack(vector<int>& frequency, int len, int idx) {
        // 遍歷所有可能的字母
        for (int i = 0; i < 26; i++) {
            // 如果這個字母沒有剩餘，則跳過
            if (frequency[i] == 0) continue;
            
            // 使用當前字母的一個實例
            frequency[i]--;
            // 遞迴調用回溯以形成更長的序列
            backtrack(frequency, len, idx + 1);
            // 回溯：恢復字母計數
            frequency[i]++;
        }
        // 增加序列計數器
        ans++;
    }
    
    int numTilePossibilities(string tiles) {
        // 初始化26個大寫字母的字母頻率數組
        vector<int> frequency(26, 0);

        // 計算輸入字母磚中的每個字母
        for (char c : tiles) {
            frequency[c - 'A']++;
        }

        // 從初始狀態開始回溯
        backtrack(frequency, tiles.size(), 0);

        return ans;
    }
};

Python

class Solution:
    # 初始化計算可能序列數量的計數器
    def __init__(self):
        self.ans = -1

    # 回溯函數來探索所有可能的序列
    def backtrack(self, frequency, len, idx):
        # 遍歷所有可能的字母
        for i in range(26):
            # 如果這個字母沒有剩餘，跳過它
            if frequency[i] == 0:
                continue
            
            # 使用當前字母的一個實例
            frequency[i] -= 1
            # 以遞迴方式調用backtrack來形成更長的序列
            self.backtrack(frequency, len, idx + 1)
            # 回溯：恢復字母數量
            frequency[i] += 1
        
        # 序列計數器增量
        self.ans += 1

    def numTilePossibilities(self, tiles):
        # 對26個大寫字母初始化字母頻率數組
        frequency = [0] * 26

        # 計算輸入tiles中每個字母的數量
        for c in tiles:
            frequency[ord(c) - ord('A')] += 1

        # 從初始狀態開始回溯
        self.backtrack(frequency, len(tiles), 0)

        return self.ans

複雜度分析

時間複雜度: $O(26^n \cdot n!)$，其中 $n$ 是輸入字串 tiles 的長度。這是因為該函數檢索了所有可能的瓷磚排列，包括重複的排列以及長度小於或等於 $n$ 的所有可能長度。由於有 26 個可能的字母，因此最多有 $26^n$ 次遞迴調用，並且在每次遞迴調用中，我們會遍歷最大的 $n$ 個元素的頻率陣列（由於 $n \leq 7$，因此階乘 $n!$ 是主導因素）。
空間複雜度: $O(n)$，其中 $n$ 是 tiles 的長度。主要空間用於遞迴回溯過程中的調用。遞迴的深度受到 tiles 長度的限制，最大為 7。

CS Note
En

Leetcode 1079. Letter Tile Possibilities

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析