题目描述

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

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

样例

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

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

算法分析

枚举

• 1、先把数字和字符对应在一个哈希表中
• 2、dfs(String digits,int u,String path)：path表示当前已经有什么元素，u表示枚举到digitis的第u个字母，从哈希表中找到第u个字母对应的几个字符，分别进行枚举拼接到path后面

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

一个数字最多有4种情况，假设有n个数字，因此$4^n$种情况是一个上限，因此时间复杂度是$O(4^n)$

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");
        }
    };
    static List<String> ans = new ArrayList<String>();
    static void dfs(String digits,int u,String path)
    {
        if(u == digits.length())
        {
            ans.add(path);
            return;
        }
        String t = map.get(digits.substring(u,u + 1));
        for(int i = 0;i < t.length();i ++)
        {
            dfs(digits,u + 1,path + t.charAt(i));
        }
    }
    public List<String> letterCombinations(String digits) {
        ans.clear();
        int n = digits.length();
        if(n == 0) return ans;
        dfs(digits,0,"");
        return ans;
    }
}

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;
    }
}