leetcode-电话号码的字母组合

╰+攻爆jí腚メ 2023-07-03 02:58 3阅读 0赞

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

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

![format_png][]

示例:

输入：“23”  
输出：\[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”\].  
说明:  
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

*  解释:我们可以使用回溯的方法进行解决问题,首先我们可以看出,我们需要使用一个散列表,也就是hashmap,类似于字典形式的样子,但是仅仅这样还不行,举个例子**23**,2对应的是abc,3对应的是def,怎么才能达到九种组合能,我们第一想的是for循环,但是这样太浪费时间了,所以我们用回溯,回溯的算法思路就是到底撤回一步,一直往上走,所以这是我们使用这个的最好解决方法
 *  看代码

class Solution { 
        HashMap<String,String> hashMap = new LinkedHashMap<>();
        List<String> output = new ArrayList<>();
        public List<String> letterCombinations(String digits) { 
            hashMap.put("2","abc");
            hashMap.put("3","def");
            hashMap.put("4","ghi");
            hashMap.put("5","jkl");
            hashMap.put("6","mno");
            hashMap.put("7","pqrs");
            hashMap.put("8","tuv");
            hashMap.put("9","wxyz");
            if(digits.length()==0)
                return output;
            else
                backfind("",digits);
            return output;
        }
        public  void backfind(String combination,String next_digits){ 
            if(next_digits.length()==0)
                output.add(combination);
            else{ 
                String digit = next_digits.substring(0,1);
                String letters = hashMap.get(digit);
                for(int i =0;i<letters.length();i++){ 
                    String letter = letters.substring(i,i+1);
                    backfind(combination+letter,next_digits.substring(1));
                }
            }
        }
    
    }

复杂度分析

时间复杂度：  O ( 3 N ∗ 4 M ) O(3^N\*4^M) O(3N∗4M) ，其中 N 是输入数字中对应 3 个字母的数目（比方说 2，3，4，5，6，8）， M 是输入数字中对应 4 个字母的数目（比方说 7，9），N+M 是输入数字的总数。

空间复杂度： O ( 3 N ∗ 4 M ) O(3^N\*4^M) O(3N∗4M)，这是因为需要保存  3 N ∗ 4 M 3^N\*4^M 3N∗4M个结果

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvb3JpZ2luYWxfaW1hZ2VzLzE3X3RlbGVwaG9uZV9rZXlwYWQucG5n?x-oss-process=image/format,png