問題鏈接

17. 電話號(hào)碼的字母組合

問題描述

給定一個(gè)僅包含數(shù)字 2-9 的字符串帅腌，返回所有它能表示的字母組合驻售。答案可以按 任意順序 返回搔预。
給出數(shù)字到字母的映射如下（與電話按鍵相同）溪北。注意 1 不對(duì)應(yīng)任何字母。

示例

輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

輸入：digits = "2"
輸出：["a","b","c"]

解題思路

1. 迭代枚舉所有可能
   這個(gè)沒啥好說的蕉扮，就是窮舉闰靴。
2. 回溯枚舉所有可能
   回溯過程中維護(hù)一個(gè)字符串，表示已有的字母排列（如果未遍歷完電話號(hào)碼的所有數(shù)字睬愤，則已有的字母排列是不完整的）。該字符串初始為空佳谦。每次取電話號(hào)碼的一位數(shù)字戴涝，從哈希表中獲得該數(shù)字對(duì)應(yīng)的所有可能的字母滋戳，并將其中的一個(gè)字母插入到已有的字母排列后面钻蔑，然后繼續(xù)處理電話號(hào)碼的后一位數(shù)字，直到處理完電話號(hào)碼中的所有數(shù)字奸鸯，即得到一個(gè)完整的字母排列咪笑。然后進(jìn)行回退操作，遍歷其余的字母排列娄涩。

代碼示例（JAVA）

1. 迭代

class Solution {
    public static List<String> letterCombinations(String digits) {
        if ("".equals(digits)) {
            return new ArrayList<>();
        }
        // 將數(shù)字到字母的映射保存到哈希表
        Map<Integer, 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");

        List<String> ans = new ArrayList<>();
        ans.add("");
        char[] chars = digits.toCharArray();
        for (int i = 0; i <= chars.length - 1; i++) {
            // 復(fù)制ans
            List<String> temp = new ArrayList<>(ans);
            ans.clear();

            String curString = map.get(chars[i] - '0');
            char[] arr = curString.toCharArray();
            for (int j = 0; j <= arr.length - 1; j++) {
                List<String> itemList = new ArrayList<>();
                for (String t : temp) {
                    itemList.add(t + arr[j]);
                }
                ans.addAll(itemList);
            }
        }
        return ans;
    }
}

2. 回溯

class Solution {
    public List<String> letterCombinations(String digits) {
        if ("".equals(digits)) {
            return new ArrayList<>();
        }
        // 將數(shù)字到字母的映射保存到哈希表
        Map<Integer, 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");

        List<String> ans = new ArrayList<>();
        recursion(new StringBuilder(""), digits, map, ans, 0);
        return ans;
    }

    public void recursion(StringBuilder s, String digits, Map<Integer, String> map, List<String> ans, int index) {
        if (index == digits.length()) {
            ans.add(s.toString());
            return;
        }

        String letters = map.get(digits.toCharArray()[index] - '0');
        for (char c : letters.toCharArray()) {
            recursion(s.append(c), digits, map, ans, index + 1);
            s.deleteCharAt(index);
        }
    }
}