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

Posted by lizhao on 07-09,2019

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

[toc]

题目

给定一个仅包含数字 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://blog.csdn.net/cmqwan

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

如有疑问请联系,联系方式:QQ3060507060