Leetcode 1079. 拼字組合數量

這是 Leetcode 2025 年 2 月 17 日的每日一題。

題目描述
#

給定 $n$ 個字母牌（例如 $AAB$），請計算使用這些字母可以組成的不重複字串總數。

解題直覺
#

每當遇到找出所有字串組合的問題時，我們第一個想到的演算法是回溯法（Backtracking）。

解題思路
#

統計每個字母的出現次數。
使用 DFS 探索所有可能的組合，每次使用一個字母後遞迴呼叫自身，並減少該字母的頻率。
回溯時，恢復該字母的頻率，確保可以嘗試所有可能。

時間複雜度：$O(N!)$，因為我們要探索所有不重複的排列。

Code
#

class Solution {
public:
    // DFS function to count all possible sequences
    int countSequences(unordered_map<char, int>& frequency){
        int result = 0;

        // Iterate over all available letters
        for(auto& pair: frequency){
            char letter = pair.first;
            if (frequency[letter] > 0){ //only deal with letter that are still available
                frequency[letter] --;  // use this letter
                result += countSequences(frequency) + 1; // Recursive call and count this sequence
                frequency[letter] ++; //backtracking, restore the frequency of the letter
            }
        }
        return result;
    }
    int numTilePossibilities(string tiles) {
        unordered_map<char, int> frequency; //To record frequency of each letter
        for(int i = 0; i < tiles.length(); i++){
            frequency[tiles[i]]++;
        }
        return countSequences(frequency);
    }
};