728x90
반응형
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
문제
문제 분석
- DFS 재귀 탐색을 이용해서 가능한 모든 경우의 수를 만들어내면 됩니다.
- 각 순서가 유지되기 때문에 단순 DFS로 풀이가 가능합니다. ("23"이면 "32"인 경우랑은 다름)
풀이
class Solution {
private:
std::map<int, std::vector<char>> keypad = {
{2, {'a', 'b', 'c'}},
{3, {'d', 'e', 'f'}},
{4, {'g', 'h', 'i'}},
{5, {'j', 'k', 'l'}},
{6, {'m', 'n', 'o'}},
{7, {'p', 'q', 'r', 's'}},
{8, {'t', 'u', 'v'}},
{9, {'w', 'x', 'y', 'z'}}
};
std::vector<std::string> result;
std::string digits;
public:
void dfs(int index, std::string path){
if (path.length() == digits.length()){
result.push_back(path);
return;
}
for(const auto& c : keypad[digits[index] - '0']){
dfs(index + 1, path + c);
}
}
std::vector<std::string> letterCombinations(std::string digits) {
if (digits.empty()) {
return result;
}
this->digits = digits;
dfs(0, "");
return result;
}
};
728x90
반응형
'Problem Solving > LeetCode' 카테고리의 다른 글
[LeetCode] C++ 77. Combinations (0) | 2024.09.01 |
---|---|
[LeetCode] C++ 46. Permutations (0) | 2024.09.01 |
[LeetCode] C++ 200. Number of Islands (0) | 2024.09.01 |
[LeetCode] C++ 706. Design HashMap (0) | 2024.08.26 |
[LeetCode] C++ 23. Merge k Sorted Lists. (0) | 2024.08.25 |