C++ recursive solution 0ms with comments!


  • 0

    Backtracking solution!

    class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            //If empty, we just return an empty vector
            if(!digits.size()) return vector<string>(); 
            
            //Set up the mapping and result vectors
            vector<string> digitMapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
            vector<string> res; 
            
            letterCombinations_helper(digits, res, digitMapping, ""); 
            
            return res;
        }
    
        void letterCombinations_helper(string digits, vector<string> &res, vector<string> &digitMapping, string currentString) {
            //If there are no digits left, then we've found a string to push into the result.
            if(!digits.size()) {
                res.push_back(currentString); 
                return;
            }
            
            //Choose the first digit in the input string and erase it from the input string. 
            int digit = digits[0] - '0'; 
            digits.erase(0, 1); 
            
            //For each character in the string mapping, we push back the character, then call the
            //function recursively for the remaining digits. We will continue doing this until 
            //there are no characters/no digitsMappings left to add. 
            for(auto i : digitMapping[digit]) {
                currentString.push_back(i); 
                letterCombinations_helper(digits, res, digitMapping, currentString);
                currentString.pop_back(); 
            }
        }
    };
    
    

Log in to reply
 

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