Letter Combinations of A Phone Number

06/25/2016 Backtracking String

Question

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Telephone Pad

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note: Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution

Result: Accepted Time: 0ms

Here should be some explanations.

class Solution {
public:
    const char *str[12] = {" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz",};
    const int  lens[12] = {  0, 0,    3,    3,    3,    3,    3,     4,    3,    4,};
    vector<string> letterCombinations(string digits) {
        const int len = digits.length();
        char tmp[32]={0};
        vector<string> ans;
        if(!len)
            return ans;
        int enm = 0,rest = 0,i,t;
        while(!rest)
        {
             for(i = 0,t,rest = enm++; i < len; i++,rest /= lens[t])/// rest /= lens[t]  and rest%lens[t] is the magic !!!!!!!
             {
                t = digits[i]-'0';
                tmp[i] = str[t][rest%lens[t]];/// Can you figure this out ?
            }
            if(!rest)   ans.push_back(tmp);
        }
        return ans;
     }
};

Complexity Analytics

  • Time Complexity:
  • Space Complexity: