Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Problem Link

Letter Combinations of a Phone Number - LeetCode

Recursion Tree for Backtracking

Code

via Backtracking

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (!digits.size()) {
            return {};
        }

        vector<string> combs;
        const vector<string> chars = { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        string builder;
        build(builder, 0, digits, chars, combs);
        return combs;
    }

    /**
     * start with an empty builder, for every digit, use all chars it represents to attach to the builder, when i reaches the end of digits, push builder to result;
     */
    void build(string builder, int i, const string& digits, const vector<string>& chars, 
vector<string>& combs) {
        if (i == digits.size()) {
            combs.push_back(builder);
            return;
        }

        int d = digits[i] - '0';
        for (char ch : chars[d]) {
            build(builder + ch, i + 1, digits, chars, combs);
        }
    }
};

Another Way

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        
        vector<string> dict = {"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        int n = digits.size();
        string temp = "";
        vector<string> res;
        if(n==0)
            return res;
      
        
        solve(digits,dict,temp,res,n,0);
        
        return res;
    }
    
    void solve(string digits,vector<string> dict,string &temp,vector<string> &res,int n,
int start)
    {
        if(start>n)
            return;
        
        if(start==n&&temp.size()==n)
        {
            res.push_back(temp);
            return;
        }
        
        for(int i=start;i<n;i++) 
        {
            int idx = digits[i]-'0';
            
            for(int j=0;j<dict[idx].size();j++)
            {
                temp.push_back(dict[idx][j]);
                solve(digits,dict,temp,res,n,i+1);
                temp.pop_back();
            }
        }
    }
};

via Iteration

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)
            return {};
        vector<string> dict = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        
        vector<string> res;
        res.push_back("");
        
        for(char digit:digits)
        {
            vector<string> temp;
            for(char ch:dict[digit-'0'])
            {
                
                for(string str:res)
                    temp.push_back(str+ch);
                
                
                
                
            }
            res=temp;
        }
        return res;
    }
};