C++ dfs solution


  • 0
    F
    class Solution {
    private:
        unordered_map<int, string> key_map;
    public:
        void expand(string &digits, string &path, int index, vector<string>& result) {
            if(index > digits.size()) return;
            if(index == digits.size() && !path.empty()) {
                result.push_back(path);
                return;
            }
            int num = digits[index] - '0';
            if(num == 1 || num == 0) {
                expand(digits, path, index + 1, result);
            } else {
                string s = key_map[num];
                for(auto c : s) {
                    path.push_back(c);
                    expand(digits, path, index + 1, result);
                    path.pop_back();
                }
            }
        }
        vector<string> letterCombinations(string digits) {
            key_map[2] = "abc";
            key_map[3] = "def";
            key_map[4] = "ghi";
            key_map[5] = "jkl";
            key_map[6] = "mno";
            key_map[7] = "pqrs";
            key_map[8] = "tuv";
            key_map[9] = "wxyz";
            
            vector<string> result;
            string path;
            expand(digits, path, 0, result);
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.