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

阳光穿透心脏的1/2处 2022-12-21 06:13 125阅读 0赞

### LeetCode 17. 电话号码的字母组合 ###

*  题目：
 *  解题方法：
 *   *  方法1：递归法
     *   *  Java实现

# 题目： #

官网直通车：[LeetCode 17. 电话号码的字母组合][LeetCode 17.]  
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。  
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。  
![17题目的图片][17]

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

# 解题方法： #

## 方法1：递归法 ##

思路：先存储好键盘数字对应的英文字母，这样子可以对给的输入字符串进行拆解，然后找出对应英文字符串进行逐个匹配匹配。  
从LeetCode官网找到下面这样图便于理解：[题解地址][Link 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Blbmd4aWFvemhlbjExMTE_size_16_color_FFFFFF_t_70_pic_center]

### Java实现 ###

class Solution {
        public List<String> letterCombinations(String digits) {
            List<String> res = new LinkedList<>();
            if (digits.length() == 0) {
                return res;
            }
            Map<Character, String> map = new HashMap<>();
            map.put('2', "abc");
            map.put('3', "def");
            map.put('4', "ghi");
            map.put('5', "jkl");
            map.put('6', "mno");
            map.put('7', "pqrs");
            map.put('8', "tuv");
            map.put('9', "wxyz");
            search("", digits, 0, res, map);
            return res;
        }
    
        public void search(String str, 
                            String digits, 
                            int level,
                            List<String> res, 
                            Map<Character, String> map) {
            // terminate
            if (level == digits.length()) {
                res.add(str);
                return;
            }
    
            // precess current logic
            String letters = map.get(digits.charAt(level));
            for (int i = 0; i < letters.length(); i++) {
                // drill down
                search(str + letters.charAt(i), digits, level + 1, res, map);
            }
    
            // reverse
        }
    }

[LeetCode 17.]: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
[17]: /images/20221120/5ac76cf4634b4be2b65dd76f16da5c35.png
[Link 1]: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Blbmd4aWFvemhlbjExMTE_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/1ba6b4ec1f0b4dc4ae22c6a08d31ee63.png