Leet Code 17.*的字母组合

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

思路

如何表示数字与字母的映射是一个问题，这个问题解决了，题目也就容易解决了。用哪个数据结构呢？Map。

2--abc
3--def
4--ghi
···

解决完映射后，将输入的数字字符串遍历，将映射中的字母循环组合，即可遍历所有能表示的字母组合。可是这样的话，好几层循环，有没有更快的遍历方式？递归。

看了网上其他人的解题方式，DFS搜索，遍历所有的可能性。也有用队列的。

提交代码

import java.util.*;

public class leetcode {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String digit_str = scan.nextLine();
        List<String> result= letterCombinations(digit_str);
        System.out.println(result);
    }

    static Map<String, String> phone = new HashMap<>(){{
        put("2","abc");
        put("3","def");
        put("4","ghi");
        put("5","jkl");
        put("6","mno");
        put("7","pqrs");
        put("8","tuv");
        put("9","wxyz");
    }};

    static List<String> output = new ArrayList<>();

    public static void backtrack(String combination, String next_digits) {
        if (next_digits.length() == 0 ) {
            output.add(combination);
        }
        else {
            String digit = next_digits.substring(0,1);
            String letters = phone.get(digit);
            for(int i =0; i<letters.length(); i++) {
                String letter = letters.substring(i,i+1);
                backtrack(combination+letter, next_digits.substring(1));
            }
        }
    }

    public static List<String> letterCombinations(String digits) {
        if(digits.length() != 0)
            backtrack("", digits);
        return output;
    }
}