DFS+Recall1

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/]

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

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

示例:

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

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

算法描述

​ 搜先定义一个空字符串，读取给的数字字符串，每次读取一个字符对应每个按键上的字符，考虑每一种可能，添加到字符串后面，一直递归下去，直到最后得到的长度为所给的数字字符串的长度，终止递归；

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        unordered_map<char, string> table{
            {'0', " "}, {'1',"*"}, {'2', "abc"},
            {'3',"def"}, {'4',"ghi"}, {'5',"jkl"},
            {'6',"mno"}, {'7',"pqrs"},{'8',"tuv"},
            {'9',"wxyz"}};  
        vector<string> res;
        if(digits == "") return res;
        func(res, "", digits, table, 0);
        return res;
    }
    
    void func(vector<string> &res, string str, string &digits, 
              unordered_map<char, string> &m, int k){
        if(str.size() == digits.size()){
            res.push_back(str);
            return;
        }
        string tmp = m[digits[k]];
        for(char w : tmp){
            str += w;
            func(res, str, digits, m, k+1);
            str.pop_back();
        }
        return ;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    
    String ss[] = {
            " ",    
            "",     
            "abc",  
            "def",  
            "ghi",  
            "jkl",  
            "mno",  
            "pqrs", 
            "tuv",  
            "wxyz"  
    };

    ArrayList<String> res;
    
    public void dfs(String d,int index,String s){
        if(index==d.length()){
            res.add(s);
            return;
        }
        char c = d.charAt(index);
       
        String n = ss[c-'0'];
        for(int i=0;i<n.length();i++){
            dfs(d,index+1,s+n.charAt(i));
        }
        return;
    }
    
    public List<String> letterCombinations(String digits) {
        res = new ArrayList<String>();
        if(digits.equals(""))return res;
        dfs(digits,0,"");
        return res;
    }
}