[LeetCode] C++ 17. Letter Combinations of a Phone Number

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;
    }
};