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.

算法一： 用数制进位的思维做组合。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        const char *map[] = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        int idx[sizeof(map)/sizeof(map[0])] = {0};
        vector<string> result;
        string item;
        bool carry = false;
        while (!carry) {
                item.clear();
                carry = true;
                for (int i=0; i<digits.size(); ++i) {
                        const char * p = &map[digits[i]-'0'][idx[i]];
                        if (*p)
                                item.append(1, *p);

                        if (carry && *p) {
                                ++idx[i];
                                ++p;
                                if (!*p)
                                        idx[i] = 0;
                                else
                                        carry = false;
                        }
                }
                result.push_back(item);
        }

        if (result.empty())
                result.push_back(item);

        return result;
    }
};

下面这一句，纯粹是为了满足leetcode的输入为空串("")时的test case：

        if (result.empty())
                result.push_back(item);

看到这算法的执行时间，忍不住做了个截图，留个纪念。

算法二，待续

Letter Combinations of a Phone Number -- leetcode