链接:https://leetcode.com/problems/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.

题意:给定一个电话号码,每个数字对应话机上的对应的某个字母,返回所有可能的字符串组合。

分析:DFS简单题,BFS也能做。

代码:

class Solution {
public:
    void init() {
        dict[2] = {'a', 'b', 'c'};
        dict[3] = {'d', 'e', 'f'};
        dict[4] = {'g', 'h', 'i'};
        dict[5] = {'j', 'k', 'l'};
        dict[6] = {'m', 'n', 'o'};
        dict[7] = {'p', 'q', 'r', 's'};
        dict[8] = {'t', 'u', 'v'};
        dict[9] = {'w', 'x', 'y', 'z'};
    }
    void dfs(string str, int d, string & digits) {
        if(d == digits.size()) res.push_back(str);
        else {
            int n = digits[d] - '0';
            for(auto i : dict[n])
                dfs(str + i, d+1, digits);
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)
            return res;
        init();
        dfs("", 0, digits);
        return res;
    }
private:
    vector<char> dict[10];
    vector<string> res;
};

欢迎留言