Day11 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回， 给出数字到字母的映射与电话按键相同

image

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

示例1：

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

示例2：

输入：digits = ""
输出：[]

示例3：

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

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

Java解法

思路：

• 这就是个排列组合的题，测试了下重复数字的结果，就搞完了，简单的不像中等题
• 按位求出当前的字母list，分别与上次的字母list进行了一一拼接，处理了下拼接优化，结果一把过

package sj.shimmer.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by SJ on 2021/2/4.
 */

class D11 {
    public static void main(String[] args) {
        System.out.println(letterCombinations("22"));

    }

    public static List<String> letterCombinations(String digits) {
        List<String> results = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return results;
        }
        StringBuilder builder = new StringBuilder();
        List<String> temps = getLetter(Integer.parseInt(String.valueOf(digits.charAt(0))));
        for (int i = 1; i < digits.length(); i++) {
            List<String> letter = getLetter(Integer.parseInt(String.valueOf(digits.charAt(i))));
            results.clear();
            for (String s : temps) {
                for (String l : letter) {
                    builder.delete(0, builder.toString().length());
                    builder.append(s);
                    builder.append(l);
                    results.add(builder.toString());
                }
            }
            temps.clear();
            temps.addAll(results);
        }

        results = temps;;
        return results;
    }

    public static List<String> getLetter(int num) {
        ArrayList<String> list = new ArrayList<>();
        switch (num) {
            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;
        }
        return list;
    }
}

image

官方解

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/

1. 回溯
   想法很高级，emmm，就是没接触过回溯思维的脑壳也能写出来

• 用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作
• 回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。
• 回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

• 时间复杂度：O(3^m *4^n)，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n是输入数字的总个数。

• 空间复杂度： O(m+n)