凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 17. Letter Combinations of a Phone Number

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


题目

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.

题意

给出一个代表数字的字符串,返回这个数字所有可能代表的字符组合。

解法

本题可以通过树的搜索来解决。 可以假设有一个 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[0] - '2'][i]; ++i) {
            string tmp = prefix;
            tmp.push_back(table[s[0] - '2'][i]);
            letterCombinations(s + 1, table, tmp, ret);
        }
    }
};