1079. Letter Tile Possibilities - medium
문제
You have a set of 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.
제한사항
- 1 <= tiles.length <= 7
- tiles consists of uppercase English letters.
입출력 예
1
2
3
4
5
6
7
8
9
10
Example 1:
Input: "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".
Example 2:
Input: "AAABBC"
Output: 188
풀이
- Recursive, BackTracking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
void backTracking(set<string>& item, string& tiles, string& subStr, vector<bool>& check){
if(subStr.size() == tiles.size()){
return;
}
// 문자를 하나씩 추가하며 전체 경우를 찾아봄
for(auto i = 0 ; i < tiles.size() ; ++i){
// 현재 문자를 이미 추가했는지 체크
if(check[i]){
subStr.push_back(tiles[i]);
// 추가한 문자가 이미 set에 있다면,
// 이후 모든 조합은 이미 있게 되는 것이므로 탐색 중지
if(item.find(subStr) != item.end()){
subStr.pop_back();
continue;
}
check[i] = false;
item.insert(subStr);
backTracking(item, tiles, subStr, check);
subStr.pop_back();
check[i] = true;
}
}
}
int numTilePossibilities(string tiles) {
set<string> item;
vector<bool> check(tiles.size(), true);
string temp;
backTracking(item, tiles, temp, check);
return item.size();
}
};