Leetcode算法Java全解答--17. 电话号码的字母组合

Dear 丶 2022-04-16 00:42 111阅读 0赞

# Leetcode算法Java全解答–17. 电话号码的字母组合 #

### 文章目录 ###

*  Leetcode算法Java全解答--17. 电话号码的字母组合
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。  
digitToLetter\[‘2’\]=“abc”;  
digitToLetter\[‘3’\]=“def”;  
digitToLetter\[‘4’\]=“ghi”;  
digitToLetter\[‘5’\]=“jkl”;  
digitToLetter\[‘6’\]=“mno”;  
digitToLetter\[‘7’\]=“pqrs”;  
digitToLetter\[‘8’\]=“tuv”;  
digitToLetter\[‘9’\]=“wxyz”;

示例：

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

## 想法 ##

1.  循环0~length-1

将原数组中的值加上当前值得可能性

比如第一个数字2,对应的就是abc，这时 候数组中的值就是\[a,b,c\]

轮到下一个数字3，对应的是def,就把a拼上d/e/f

返回数组  
2. 回溯法

把每个数字当作递归的一层，每一层中先枚举一个字母，

递归进入下一层，再删除这个字母，回到上一个状态，枚举下一个字母。

递归结束标志是递归了digits.lengtgh层，即字母组合长度等于digits长度，

递归结束得到一个符合的字母组合，加入list。等于是在循环中套递归

## 结果 ##

*      超过99%的测试案例
 *      时间复杂度：n2
 *      空间复杂度：n

## 总结 ##

没有用递归的方式，直接使用迭代的方法

## 代码 ##

### 我的答案 ###

/**************************************
    * 题目
    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
    
    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
    digitToLetter['2']="abc";
    digitToLetter['3']="def";
    digitToLetter['4']="ghi";
    digitToLetter['5']="jkl";
    digitToLetter['6']="mno";
    digitToLetter['7']="pqrs";
    digitToLetter['8']="tuv";
    digitToLetter['9']="wxyz";
    
    示例:
    
    输入："23"
    输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
    说明:
    尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
    **************************************/
    
    /**************************************
    *
    * 想法：
    *      1. 循环0~length-1
    *          将原数组中的值加上当前值得可能性
    *              比如第一个数字2,对应的就是abc，这时候数组中的值就是[a,b,c]
    *              轮到下一个数字3，对应的是def,就把a拼上d/e/f
    *          返回数组
    *      2. 回溯法
    *          把每个数字当作递归的一层，每一层中先枚举一个字母，
    *          递归进入下一层，再删除这个字母，回到上一个状态，枚举下一个字母。
    *          递归结束标志是递归了digits.lengtgh层，即字母组合长度等于digits长度，
    *          递归结束得到一个符合的字母组合，加入list。等于是在循环中套递归
    * 我的做法
    *      超过99%的测试案例
    *      时间复杂度：n2
    *      空间复杂度：n
    * 代码执行过程：
    *
    * 总结：
    *      没有用递归的方式，直接使用迭代的方法
    *
    *
    * ***********************************/
    public List<String> letterCombinations(String digits) {
    
    if (digits.length() == 0) {
        return Collections.EMPTY_LIST;
    }
    
    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");
    
    char[] chars = digits.toCharArray();
    List<String> result = new ArrayList<>();
    result.add("");
    
    for (char c : chars) {
        List<String> tmpList = new ArrayList<>();
        String sufStr = map.get(c);
        for (String str : result) {
            for (Character tmpC : sufStr.toCharArray()) {
                String tmpStr = str + tmpC;
                tmpList.add(tmpStr);
            }
        }
        result = tmpList;
    }
    
    return result;
    }

### 大佬们的答案 ###

/**************************************
     * 比我好的答案 better
     * ***********************************/
    public List<String> better(String digits) {
        List<String> res = new ArrayList<>();
        String oneRes = "";
        if (digits.equals("")) {
            return res;
        }
        String[] dict = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        int[] digiInt = new int[digits.length()];
        for (int i = 0; i < digits.length(); i++) {
            digiInt[i] = digits.charAt(i) - '0';
        }
    
        combi(digiInt, 0, dict, res, oneRes);
        return res;
    }
    
    public void combi(int[] digits, int n, String[] dict, List<String> res, String oneRes) {
        if (n == digits.length) {
            res.add(oneRes);
            return;
        }
        for (int j = 0; j < dict[digits[n]].length(); j++) {
            oneRes = oneRes + dict[digits[n]].charAt(j);
            combi(digits, n + 1, dict, res, oneRes);
            oneRes = oneRes.substring(0, oneRes.length() - 1);
        }
    }

### 测试用例 ###

@Test
    public void test017() {
        // 创建测试案例
        String str1 = "23";
    
        // 测试案例期望值
        String[] strings = new String[] { "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" };
        List<String> expResult1 = Arrays.asList(strings);
        //        expResult1.addAll(strings);
    
        // 执行方法
        Solution017 solution017 = new Solution017();
        List<String> result1 = solution017.letterCombinations(str1);
        List<String> result11 = solution017.better(str1);
    
        // 判断期望值与实际值
        Assert.assertEquals(expResult1, result1);
        Assert.assertEquals(expResult1, result11);
    
    }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan