Leetcode Problem:
Summary
- The problem is to find the number of possible non-empty sequences of letters that can be made using the letters printed on the tiles.
Approach
- The solution uses a recursive approach with backtracking
- It checks all possible combinations of letters and stores the valid sequences in a set.
Complexity
- O(2^n * n) where n is the length of the tiles string
Explanation
- The solution uses a recursive function checkCnt to generate all possible sequences of letters
- It uses a set to store the valid sequences and a visited array to prevent duplicate sequences
- The function checks all possible combinations of letters and adds the valid sequences to the set
- Finally, it returns the size of the set, which represents the number of possible non-empty sequences of letters.
Solution Code:
class Solution {
public:
bool visited[7];
set s;
void checkCnt(string &tiles, string letters, int length, int depth){
if(length == depth){
s.insert(letters);
return;
}
for(int i = 0 ; i < tiles.size(); i++){
if(visited[i]) continue;
visited[i] = true;
checkCnt(tiles, letters + tiles[i], length + 1, depth);
visited[i] = false;
}
}
int numTilePossibilities(string tiles) {
for(int i = 1; i <= tiles.size(); i++){
checkCnt(tiles, "", 0, i);
}
return s.size();
}
};
class Solution {
public:
bool visited[7];
set s;
void checkCnt(string &tiles, string letters, int length, int depth){
if(length == depth){
s.insert(letters);
return;
}
for(int i = 0 ; i < tiles.size(); i++){
if(visited[i]) continue;
visited[i] = true;
checkCnt(tiles, letters + tiles[i], length + 1, depth);
visited[i] = false;
}
}
int numTilePossibilities(string tiles) {
for(int i = 1; i <= tiles.size(); i++){
checkCnt(tiles, "", 0, i);
}
return s.size();
}
};
'알고리즘' 카테고리의 다른 글
| Smallest Range Covering Elements from K Lists (0) | 2025.02.18 |
|---|---|
| The Number of the Smallest Unoccupied Chair (0) | 2025.02.18 |
| Maximum Width Ramp (1) | 2025.02.17 |
| Minimum Number of Swaps to Make the String Balanced (0) | 2025.02.17 |
| Minimum String Length After Removing Substrings (0) | 2025.02.17 |
짬뽕얼큰하게
