学步园

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);

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

算法二，字符逐步添加法

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        const char *map[] = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> result;
        result.push_back("");

        for (int i=0; i<digits.size(); i++) {
                const int idx = digits[i] - '0';
                if (!*map[idx]) continue;

                const size_t size = result.size();
                for (int j=0; j<size; j++) {
                        const char *p = map[idx];
                        while (*++p) {
                                result.push_back(result[j]);
                                result[result.size()-1].append(1, *p);
                        }
                        result[j].append(1, *map[idx]);
                }
        }

        return result;
    }
};

这个算法在leetcode上实际执行时间也为4 ms。

算法三，递归

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        string item;
        permutate(result, digits, 0, item);
        return result;
    }

    void permutate(vector<string> &res, const string &digits, size_t idx, string &item) {
        if (idx == digits.size())
                return res.push_back(item);

        static const char *map[] = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        const char *p = map[digits[idx] - '0'];
        while (*p) {
                item.push_back(*p);;
                permutate(res, digits, idx+1, item);
                item.pop_back(); // c++ 11
                ++p;
        }
    }
};

这个算法执行时间也是4ms。看来这道题，怎么写都是4ms。

这三个算法，都包含了对数字1的处理，1对应着一个空字符串。

不过leetcode上test case并未包含1的情况。所以即使不对1作特殊处理，也能被AC。