算法小知识—-11.25—-电话号码的字母组合

这是我参与11月更文挑战的第25天，活动详情查看：2021最后一次更文挑战

电话号码的字母组合

该题出自力扣的17题——电话号码的字母组合（中等题）

审题

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
复制代码

• 简单概括就是，需要自己维护一套数字对应的字符，就像我们日常的九宫格键盘一样，在这个的基础上，对每一个进行拼接

• 由于维护一套hashMap去存储数字对应的字符需要额外开辟空间，所以这边利用switch/case去实现

• 解决方法采用递归去实现：

  • 如果当前长度为空，则直接返回空list
  • 如果当前长度<2,则返回对应数字的字符
  • 获取当前的字符串的首位字符去作为循环拼接
  • 截取当前字符串的次位开始到末尾，进行递归遍历
  • 双重for循环
  • 拼接字符串

编码

回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        if (digits.isEmpty()){return list;}
        else if (digits.length()<2){return matchLetter(Integer.valueOf(digits));}
        List<String> nowList = matchLetter(Integer.valueOf(digits.substring(0,1)));
        List<String> oldList = letterCombinations(digits.substring(1));
        for (int i = 0; i < nowList.size(); i++) {
            for (int j = 0; j < oldList.size(); j++) {
                list.add(i,addLetter(nowList.get(i),oldList.get(j)));
            }
        }
        return list;
    }
​
    public String addLetter(String a, String b){
        StringBuilder sb = new StringBuilder(a);
        sb.append(b);
        return sb.toString();
    }
​
    public List<String> matchLetter(Integer a){
        List<String> list = new ArrayList<>();
        switch (a){
            case 2:
                list.add("a");
                list.add("b");
                list.add("c");
                break;
            case 3:
                list.add("d");
                list.add("e");
                list.add("f");
                break;
            case 4:
                list.add("g");
                list.add("h");
                list.add("i");
                break;
            case 5:
                list.add("j");
                list.add("k");
                list.add("l");
                break;
            case 6:
                list.add("m");
                list.add("n");
                list.add("o");
                break;
            case 7:
                list.add("p");
                list.add("q");
                list.add("r");
                list.add("s");
                break;
            case 8:
                list.add("t");
                list.add("u");
                list.add("v");
                break;
            case 9:
                list.add("w");
                list.add("x");
                list.add("y");
                list.add("z");
                break;
            default:
                break;
        }
        return list;
    }
复制代码