DFS-based Solution for the Letter Combinations of a Phone Number problem (C++)


  • 0
    F
    void DFSVisit(const string &input, const string &str, size_t nextDigit, const int *maxLetters, const char **letterNumsMap, vector<string> & combinations) {
        if (nextDigit >= input.size()) return;
        int d = input[nextDigit]-48;
        for (size_t j = 0; j < maxLetters[d]; j++) {
            string newStr = str;
            newStr += letterNumsMap[d][j];
            if (nextDigit+1 >= input.size()) {
                combinations.push_back(newStr);
            } else {
                DFSVisit(input,newStr,nextDigit+1,maxLetters,letterNumsMap,combinations);
            }
        }
        return ;
    }
    
    vector<string> letterCombinations(string digits) {
        vector<string> combinations;
        int maxLetters[10] = {0,0,3,3,3,3,3,4,3,4};
        const char *letterNumsMap[] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        string str = "";
        
        if (digits.size() < 1) return combinations;
        
        DFSVisit(digits, str, 0, maxLetters, letterNumsMap, combinations);
        
        return combinations;
    }

Log in to reply
 

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