电话号码的字母组合

今天的题目是电话号码的字母组合。

我们先来看下题目要求：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

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

读完题，我们根据题意不难得出，题解是：求出所有输入的数字可能对应的字母组合，
如：① 2：‘'a",“b”,“c”
② 3：“d”，“e”，“f”
①和②组合搭配，可能返回的所有两位的字母。

如果还是没明白，还是来画出递归图读懂题意吧！

画着画着是不是就真的明白这个题大概啥意思啦！！好了，我们已经可以判定这个题可以使用深度优先搜索来做啦？

那么老规矩，先找出递归三要素。

一，函数设计

我们把可能出现的情况画出来，发现是个递归树，自然要传入一个数字 level表示需要遍历的层数，temp是为了存储临时变量，用StringBuilder而不用String是因为需要频繁修改，性能更高

     /**
     * 
     * @param level 当前树的层数
     * @param temp  用来存储临时的值的容器，符合条件就放list中，不符合就回溯
     */
    public void dfs(int level , StringBuilder temp) {

二，终止条件

输入几个数，level就是几，超出这个数就跳出循环

	 if (level >= input.length()) { // ②终止条件： 输入几个数字就是几层 超出就代表着已遍历完了

三，递归方向

输入的第 i 个数里头有几个元素 就有几个递归方向
需要注意的是回溯操作，回溯可以理解为将上一层树 （level）递归时产生的不符合条件的树杈干掉，换别的树杈

注：(因为符合条件就跳到终止条件了，那么最后一层不符合条件，但是也被存进ArrayList中了，不能让他把不符合的带走，所以需要回溯)

       //递归方向：每一个输入的数字有几个元素就代表着几个方向
        int num = (int) input.charAt(level) - '0';
        for (int i = 0; i < chars[num].length; i++) {
            dfs(level+1 , temp.append(chars[num][i]));
            temp.deleteCharAt(temp.length() - 1); 
        }

函数体在这里，我们写这个函数来调递归函数。

在这里插入代码片
  public List<String> letterCombinations(String digits){
        input = digits;
        if (!Objects.nonNull(digits))
            if (Integer.parseInt(digits) >=2 && Integer.parseInt(digits) <=9)
                return new ArrayList<>();
        res = new ArrayList<>();
        dfs(0,new StringBuilder());
        return res;
    }
    String input;
    ArrayList<String> res;

完整的代码在这里：

在这里插入代码片
 char[][] chars = {{},{},{'a','b','c'},{'d','e','f'},
            {'g','h','i'},{'j','k','l'},{'m','n','o'},
            {'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}
    };
    public List<String> letterCombinations(String digits){
        input = digits;
        if (!Objects.nonNull(digits))
            if (Integer.parseInt(digits) >=2 && Integer.parseInt(digits) <=9)
                return new ArrayList<>();
        res = new ArrayList<>();
        dfs(0,new StringBuilder());
        return res;
    }
    String input;
    ArrayList<String> res;

    /**
     *
     * @param level 当前树的层数
     * @param temp  用来存储临时的值的容器，符合条件就放list中，不符合就回溯
     */
    public void dfs(int level , StringBuilder temp) {
        if (level >= input.length()) { // ②终止条件： 输入几个数字就是几层 超出就代表着已遍历完了
            res.add(temp.toString()); //将遍历完的数据添加到集合中
            return;
        }
        //递归方向：每一个输入的数字有几个元素就代表着几个方向
        int num = (int) input.charAt(level) - '0';
        for (int i = 0; i < chars[num].length; i++) {
            dfs(level+1 , temp.append(chars[num][i]));
            temp.deleteCharAt(temp.length() - 1); //回溯操作，将上一层树递归时产生的不符合条件的树杈干掉，换别的树杈(因为符合条件就跳到终止条件了)
        }
    }

OK，程序写完啦，我们在main方法中测试下

搞定！

2020年11月25日21:18:01