凌云的博客

LeetCode 算法题 17. 电话号码的字母组合

分类：algorithm| 发布时间：2016-07-04 12:47:00

---

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解法

本题可以通过树的搜索来解决。 可以假设有一个 root 节点， 每遇到一个数字时就是分成这个数字所代表的多个子节点， 当遇到 '\0' 时就是到达树的叶子节点了。 而每一条从 root 到 leaf 的节点所代表字符的组合就是一种可能的组合。 遍历整棵树就可以得到所有可能的组合。 可以用 BFS 或者 DFS，使用递归可以很容易地实现 DFS。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        static const  vector<string> table = {
            "abc",      // number 2
            "def",      // number 3
            "ghi",      // number 4
            "jkl",      // number 5
            "mno",      // number 6
            "pqrs",     // number 7
            "tuv",      // number 8
            "wxyz",     // number 9
        };

        vector<string> ret;
        string prefix;
        letterCombinations(digits.c_str(), table, prefix, ret);
        return ret;
    }

private:
    void letterCombinations(const char *s, const vector<string> &table,
                            const string &prefix, vector<string> &ret) {
        if (!*s) {
            if (!prefix.empty()) ret.push_back(prefix);
            return;
        }

        for (int i = 0; table[*s - '2'][i]; ++i) {
            prefix.push_back(table[*s - '2'][i]);
            letterCombinations(s + 1, table, prefix, ret);
            prefix.pop_back();
        }
    }
};