題目

image.png

思路

字符轉數(shù)字
數(shù)字轉字符
字符串拼接

題解

題解1：回溯 DFS

image.png

// 回溯和DFS的區(qū)別
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);
        //     // 字符轉數(shù)字 Integer.parseInt(str) // s - '0'
        //     // 數(shù)字轉字符 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 中第一個數(shù)字對應的每一個字母入隊，然后將出隊的元素與第二個數(shù)字對應的每一個字母組合后入隊...直到遍歷到 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

題解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存儲數(shù)字與字母的映射關系
    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的長度，每次遞歸就遍歷到一個數(shù)字
        String str = map[c-'0']; //step2:獲取數(shù)字對應字符串

        for(int i=0; i<str.length(); i++){ //step3:遍歷數(shù)字對應的字符串
            sb.append(str.charAt(i)); //將遍歷到的字母加入sb
            dfs(digits,sb,pos+1); //steo4: 調(diào)用下一層遞歸
            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/