面试经典-电话号码的字母组合

电话号码的字母组合

一、题目

17. 电话号码的字母组合

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

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

示例 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'] 的一个数字。

二、题解

题解一（无递归）

class Solution {
    public List<String> letterCombinations(String digits) {
        HashMap<Character, List<String>> hashMap = new HashMap<>();
        hashMap.put('2', List.of("a", "b", "c"));
        hashMap.put('3', List.of("d", "e", "f"));
        hashMap.put('4', List.of("g", "h", "i"));
        hashMap.put('5', List.of("j", "k", "l"));
        hashMap.put('6', List.of("m", "n", "o"));
        hashMap.put('7', List.of("p", "q", "r", "s"));
        hashMap.put('8', List.of("t", "u", "v"));
        hashMap.put('9', List.of("w", "x", "y", "z"));
        if (digits.isEmpty()) {
            return List.of();
        }
        char[] charArray = digits.toCharArray();
        List<String> result = hashMap.get(charArray[0]);
        int length = digits.length();
        if (length == 1) {
            return result;
        }
        int i = 1;
        while (i < length) {
            List<String> temp = new ArrayList<>();
            for (String s1 : result) {
                for (String s2 : hashMap.get(charArray[i])) {
                    temp.add(s1 + s2);
                }
            }
            result = temp;
            i++;
        }
        return result;
    }
}

题解二（递归）

class Solution {

    static HashMap<Character, List<String>> hashMap = new HashMap<>();
    static {
        hashMap.put('2', List.of("a", "b", "c"));
        hashMap.put('3', List.of("d", "e", "f"));
        hashMap.put('4', List.of("g", "h", "i"));
        hashMap.put('5', List.of("j", "k", "l"));
        hashMap.put('6', List.of("m", "n", "o"));
        hashMap.put('7', List.of("p", "q", "r", "s"));
        hashMap.put('8', List.of("t", "u", "v"));
        hashMap.put('9', List.of("w", "x", "y", "z"));
    }

    public static List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) {
            return List.of();
        }
        char[] charArray = digits.toCharArray();
        List<String> result = hashMap.get(charArray[0]);
        int length = digits.length();
        if (length == 1) {
            return result;
        }
        return combine(1, digits,digits.length(), result);
    }

    private static List<String> combine(int i, String digits, int length, List<String> result) {
        if (i == length) {
            return result;
        }
        List<String> re = new ArrayList<>();
        List<String> strings = hashMap.get(digits.charAt(i));
        for (String s : result) {
            for (String string : strings) {
                re.add(s + string);
            }
        }
        return combine(++i, digits, length, re);
    }
}

三、总结

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

public class LetterCombinations {

    static HashMap<Character, List<String>> hashMap = new HashMap<>();
    static {
        hashMap.put('2', List.of("a", "b", "c"));
        hashMap.put('3', List.of("d", "e", "f"));
        hashMap.put('4', List.of("g", "h", "i"));
        hashMap.put('5', List.of("j", "k", "l"));
        hashMap.put('6', List.of("m", "n", "o"));
        hashMap.put('7', List.of("p", "q", "r", "s"));
        hashMap.put('8', List.of("t", "u", "v"));
        hashMap.put('9', List.of("w", "x", "y", "z"));
    }

    public static void main(String[] args) {
        String digits = "2345";
        List<String> result = letterCombinations(digits);
        for (String s : result) {
            System.out.println(s);
        }
        System.out.println(result.size());
    }

    public static List<String> letterCombinationsNoRecursion(String digits) {
        if (digits.isEmpty()) {
            return List.of();
        }
        char[] charArray = digits.toCharArray();
        List<String> result = hashMap.get(charArray[0]);
        int length = digits.length();
        if (length == 1) {
            return result;
        }
        int i = 1;
        while (i < length){
            List<String> temp = new ArrayList<>();
            for (String s1 : result) {
                for (String s2 : hashMap.get(charArray[i])) {
                    temp.add(s1+s2);
                }
            }
            result = temp;
            i++;
        }
        return result;
    }

    public static List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) {
            return List.of();
        }
        char[] charArray = digits.toCharArray();
        List<String> result = hashMap.get(charArray[0]);
        int length = digits.length();
        if (length == 1) {
            return result;
        }
        return combine(1, digits,digits.length(), result);
    }

    private static List<String> combine(int i, String digits, int length, List<String> result) {
        if (i == length) {
            return result;
        }
        List<String> re = new ArrayList<>();
        List<String> strings = hashMap.get(digits.charAt(i));
        for (String s : result) {
            for (String string : strings) {
                re.add(s + string);
            }
        }
        return combine(++i, digits, length, re);
    }
}