17. Letter Combinations of a Phone Number

problem description

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

Input: "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.

algorithm thought

典型的回溯法，没有任何需要剪枝的地方，直接深度优先遍历所有的结果，并保存。

code

class Solution {
public:
    string ma[8]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if(digits.size()==0)
            return res;
        conbin(res,digits,0,"");
        return res;
        
    }
    void conbin(vector<string>& res,string digits,int pos,string tmp){
        if(pos==digits.size()){
            res.push_back(tmp);
            return;
        }
        int num=int(digits[pos]-'0')-2;
        for(int i=0;i<ma[num].size();++i){
            conbin(res,digits,pos+1,tmp+ma[num][i]);
        }
        
    }
};

algorithm analysis

每个数字代表3-4个字符，如果都是代表3个字符。那么每次遍历的通量就是3个，如果输入digits size是n

时间复杂度就是O(3^n)