LeetCode17 电话号码的数字组合

题解思路来源：小呆呆

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

样例

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

算法分析

暴力搜索、dfs问题

时间复杂度$O(4^{n})$

一个数字最多4中情况

Java代码

class Solution {
    static HashMap<String,String> map = new HashMap<String,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");
        }
    };

    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<String>();
        int n = digits.length();
        if(n==0) return ans;
        ans.add("");
        for(int i = 0; i < n; i++){
            List<String> t = new ArrayList<String>();
            String num = digits.substring(i,i+1);
            String s  = map.get(num);
            for(int j = 0;j < s.length(); j++){
                String e = s.substring(j, j+1);
                for(String x:ans){
                    t.add(x+e);
                }
            }
            ans = t;
        }

        return ans;

    }
}