C++: Letter Combinations of a Phone Number

Thought Process

The problem requires generating all possible combinations of letters corresponding to the digits of a phone number. We use backtracking to explore all possible combinations. First, we map each digit to its corresponding letters using a dictionary. Then, we recursively build combinations by appending one letter at a time to a temporary string ( 'tmp'). When the size of 'tmp' matches the length of the input digits, we add it to the result. This ensures we explore all possible combinations without missing any. 

class Solution {
public:
    void backTrack(vector<string>& ans, map<int,string> mp, string& tmp, string digits,int start){

        // If constructed string size = digits size
        if(tmp.size()==digits.size()){
            ans.push_back(tmp);
            return;
        }

        for(int i=start;i<digits.size();i++){

            int num = digits[i]-'0';
            string str = mp[num];
            for(int j=0;j<str.size();j++){

                tmp.push_back(str[j]); // Add a character into tmp string
                backTrack(ans,mp,tmp,digits,i+1); // Try to construct the solution, with modified tmp string.
                tmp.pop_back(); // Remove the added character from the tmp string.
            }
        }
        
    }
    vector<string> letterCombinations(string digits) {
        
        string tmp;
        vector<string> ans;
        map<int,string> mp;

        mp.insert({2,"abc"});     mp.insert({3,"def"});     mp.insert({4,"ghi"});
        mp.insert({5,"jkl"});     mp.insert({6,"mno"});     mp.insert({7,"pqrs"});
        mp.insert({8,"tuv"});     mp.insert({9,"wxyz"});

        if(digits.empty())
            return ans;
        else{
            backTrack(ans,mp,tmp,digits,0);
            return ans;
        }
    }
};

Code Complexity

Time Complexity: O(4n)

In the worst case, each digit maps to 4 letters, and we explore all possible combinations.

Space Complexity: O(n)

The space is used for the recursion stack and storing the result, which depends on the input size.

Code copied!