Letter Combinations of a Phone Number

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.

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.

tag: backtracking, string

虽然tag里有回溯，但我却没想出回溯的算法。直接深搜，postorder traversal。然后在字符串的首部添加该层的字符，再把结果返回上一层。

在字符串拼接中‘+’运算符很好用。它可以连接字符与字符串，或者字符串与字符串。(concatenates two strings or a string and a char)

这里建议把键盘上的数字与字符的对应关系存在类的成员变量中，方便各个函数的调用，不用写长长的switch或if语句，代码会更简洁。

class Solution {
public:
    vector<string> data;
    vector<string> letterCombinations(string digits){
        data.push_back("");//0
        data.push_back("");//1
        data.push_back("abc");//2
        data.push_back("def");//3
        data.push_back("ghi");//4
        data.push_back("jkl");//5
        data.push_back("mno");//6
        data.push_back("pqrs");//7
        data.push_back("tuv");//8
        data.push_back("wxyz");//9
        return _letterCombinations(digits);
    }
    vector<string> _letterCombinations(string digits) {
        if (digits.size() == 0){
            vector<string> re;
            re.push_back("");
            return re;
        }
        if (digits.size() == 1){
            vector<string> re;
            char c = digits[0];
            for(int i = 0; i < data[c - '0'].size(); i++){
                 string s;
                 s.push_back(data[c - '0'][i]);
                 re.push_back(s);
            }
            return re;
        }
        else{//size > 1
            vector<string> re;
            vector<string> lastRe = _letterCombinations(digits.substr(1));
            char c = digits[0];
            for(int i = 0; i < data[c - '0'].size(); i++){
                for(int j = 0; j < lastRe.size(); j++){
                    re.push_back(data[c - '0'][i] + lastRe[j]);
                }
            }
            return re;
        }
    }
};