Last Updated on 2025-02-17 by Clay
題目
You have n tiles, where each tile has one letter tiles[i] printed on it.
Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.
Example 1:
Input: tiles = "AAB" Output: 8 Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".
Example 2:
Input: tiles = "AAABBC" Output: 188
Example 3:
Input: tiles = "V" Output: 1
Constraints:
tiles consists of uppercase English letters.
1 <= tiles.length <= 7
題目本質上是不重複的所有排列組合數量，並允許只取 1 ... tiles.length 的長度。
解題思路
一開始我總想著套用數學公式來解題，但我想來想去還是推不出公式... （汗顏）最後還是回歸到了工程師擅長的暴力破解 —— 遞迴遍歷全部組合。
我認為重點在於其實是把 AAABB 這樣的輸入，理解為 {"A": 3, "B": 2} 這樣的字典，然後我們在每個時間點，只能從字典中選擇一個字母（letter）出來組成當下的排列，並且把排列的計數 + 1、字典中可選的字母數量 - 1。
計算完之後，我們需要把當前殘存的字典狀態繼續往下走遞迴，一直到字典中沒有可選的字母時才停止計數；與此同時，也要記得在遞迴結束後把字典的狀態還原回來（也就是把當下字母數量 - 1 的部份，在走完遞迴後 + 1 回來），畢竟在我們取下一個字典的字母時，前一個取的字母還是完整的。
簡單來說，假設我們現在當前狀態取了 A ，我們的字典應該變成了 {"A": 2, "B": 2}，但是當我們準備在當前狀態取 B 時，我們需要先把字典還原回初始狀態 {"A": 3, "B": 2}，不然就會在取 B 後，突然發現字典的 AB 雙雙減少了，變成 {"A": 2, "B": 1}。
複雜度
Time Complexity = O(n!) （假設沒有重複的情況，時間複雜度應應在 n!，實際上因為字母會重複，複雜度應該更小一點）
Space Complexity = O(n)
C++ 範例程式碼
class Solution {
public:
void DFS(unordered_map<char, int>& char2times, int& count) {
for (const auto& [c, times] : char2times) {
if (times == 0) {
continue;
}
// Recursive
--char2times[c];
++count;
DFS(char2times, count);
// Recovery
++char2times[c];
}
}
int numTilePossibilities(string tiles) {
// Init
int count = 0;
std::unordered_map<char, int> char2times;
for (char& c: tiles) {
++char2times[c];
}
DFS(char2times, count);
return count;
}
};Python 範例程式碼
class Solution:
def DFS(self) -> None:
for tile, times in self.tile2times.items():
if times == 0:
continue
self.tile2times[tile] -= 1
self.count += 1
self.DFS()
self.tile2times[tile] += 1
def numTilePossibilities(self, tiles: str) -> int:
# Init
self.count = 0
self.tile2times = {}
for tile in tiles:
self.tile2times[tile] = self.tile2times.get(tile, 0) + 1
# DFS
self.DFS()
return self.count