Leetcode-17-电话号码的字母组合

题目

image.png

思路

字符转数字
数字转字符
字符串拼接

题解

题解1：回溯 DFS

image.png

// 回溯和DFS的区别
class Solution {
    // 怎么设置，哈希表么？？
    // String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) {    //
            return res;
        }
        // // for (int i = 0; i < digits.size(); i++) {
        // for (int i = 0; i < digits.length; i++) {
        //     char cur = digits.charAt(i);
        //     // 字符转数字 Integer.parseInt(str) // s - '0'
        //     // 数字转字符 it.toString()
        //     String next = map[cur - '0'];
        //     for (int j = 0; j < next.length; j++) {
        //         // 怎么放进res
        //     }
        // }
        dfs(digits, res, "", 0);
        return res;
    }
    public void dfs(String digits, List<String> res, String result, int index) {
        // if (index == digits.size()) {
        if (index == digits.length()) {         // length()
            res.add(result);
            return;
        }
        char cur = digits.charAt(index);
        String next = map[cur - '0'];
        for (int j = 0; j < next.length(); j++) {
            dfs(digits, res, result + next.charAt(j), index + 1);
        }
        return;
    }
}

题解2：BFS

队列的使用方法见下面链接动图演示
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/tong-su-yi-dong-dong-hua-yan-shi-17-dian-hua-hao-m/
先将输入的 digits 中第一个数字对应的每一个字母入队，然后将出队的元素与第二个数字对应的每一个字母组合后入队...直到遍历到 digits 的结尾。最后队列中的元素就是所求结果。

注意：有个坑 Map<Character, String>

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0 || digits.isEmpty()) {
            return res;
        }
        // 大坑啊，后面charAt取元素，所以map设置要为Map<Character, String>
        // Map<String, 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");
        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");
        res.add("");
        for (int i = 0; i < digits.length(); i++) {
            String cur = map.get(digits.charAt(i));
            int cnt = res.size();
            while (cnt != 0) {
                for (int j = 0; j < cur.length(); j++) {
                    res.add(res.get(0) + cur.charAt(j));
                }
                res.remove(0);
                cnt--;
            }
        }
        return res;
    }
}

queue

image.png

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/shou-hua-tu-jie-liang-chong-jie-fa-dfshui-su-bfsya/

题解3

字符串拼接
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/17-dian-hua-hao-ma-de-zi-mu-zu-he-hui-su-javadai-m/
StringBuilder s = new StringBuilder();
s.toString();
s.length()
s.deleteCharAt()
s.append()

class Solution {
     //map存储数字与字母的映射关系
    private String[] map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    private List<String> res = new ArrayList<String>(); //结果集
    
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0 || digits==null)    return res; //特判
        StringBuilder sb = new StringBuilder(); //存储中间结果
        dfs(digits,sb,0);
        return res;
    }
    public void dfs(String digits,StringBuilder sb, int pos){
        //pos为当前字符串temp的长度

        //递归出口，字符串temp的长度==digits的长度
        if(pos == digits.length()){
            res.add(sb.toString());
            return;
        }
        char c = digits.charAt(pos); //step1:len从0～digits的长度，每次递归就遍历到一个数字
        String str = map[c-'0']; //step2:获取数字对应字符串

        for(int i=0; i<str.length(); i++){ //step3:遍历数字对应的字符串
            sb.append(str.charAt(i)); //将遍历到的字母加入sb
            dfs(digits,sb,pos+1); //steo4: 调用下一层递归
            sb.deleteCharAt(sb.length()-1); //撤销选择  /////
        }
    }
}

参考

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/tong-su-yi-dong-dong-hua-yan-shi-17-dian-hua-hao-m/
python
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/hui-su-dui-lie-tu-jie-by-ml-zimingmeng/

image.png

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/shou-hua-tu-jie-liang-chong-jie-fa-dfshui-su-bfsya/