【leetcode】电话号码的字母组合

【leetcode】电话号码的字母组合

题目：

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

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

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解法一：迭代法

将原数组中的值加上当前值得可能性进行组合，

比如第一个数字2,对应的就是abc，这时 候数组中的值就是[a,b,c]

轮到下一个数字3，对应的是def,就把a拼上d/e/f，b拼上d/e/f，c拼上d/e/f， 返回数组

java代码：

class Solution {
    public List<String> letterCombinations(String digits) {
        HashMap<Character, String[]> map = new HashMap<>();
        map.put('2', new String[]{"a", "b", "c"});
        map.put('3', new String[]{"d", "e", "f"});
        map.put('4', new String[]{"g", "h", "i"});
        map.put('5', new String[]{"j", "k", "l"});
        map.put('6', new String[]{"m", "n", "o"});
        map.put('7', new String[]{"p", "q", "r", "s"});
        map.put('8', new String[]{"t", "u", "v"});
        map.put('9', new String[]{"w", "x", "y", "z"});
 
        int len = digits.length();
        List<String> res = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            String[] tmp = map.get(digits.charAt(i));
            List<String> listTmp = new ArrayList<>();
            if (i == 0) {
                for (String s : tmp) {
                    res.add(s);
                }
            } else {
                for (int j = 0; j < res.size(); j++) {
                    for (String s : tmp) {
                        listTmp.add(res.get(j) + s);
                    }
                }
                res = listTmp;
            }
        }
 
        return res;
    }
}

解法二：回溯法

把每个数字字符当作递归的一层，每一层中先枚举一个字母，

递归进入下一层，再删除这个字母，回到上一个状态，枚举下一个字母。

递归结束标志是递归了digits.length层，即字母组合长度等于digits长度，

递归结束得到一个符合的字母组合，加入list。等于是在循环中套递归

java代码：

class Solution {
    public List<String> letterCombinations(String digits) {
        Map<Character, String[]> map = new HashMap<>();
        map.put('2', new String[]{"a", "b", "c"});
        map.put('3', new String[]{"d", "e", "f"});
        map.put('4', new String[]{"g", "h", "i"});
        map.put('5', new String[]{"j", "k", "l"});
        map.put('6', new String[]{"m", "n", "o"});
        map.put('7', new String[]{"p", "q", "r", "s"});
        map.put('8', new String[]{"t", "u", "v"});
        map.put('9', new String[]{"w", "x", "y", "z"});
 
        int len = digits.length();
        List<String> res = new ArrayList<>();
 
        if (len == 0) {
            return res;
        }
 
        String oneRes = "";
        combi(digits, 0, res, oneRes, map);
 
        return res;
    }
 
    private void combi(String digits, int i, List<String> res, String oneRes, Map<Character, String[]> map) {
        if (i == digits.length()) {
            res.add(oneRes);
            return;
        }
 
        String[] tmp = map.get(digits.charAt(i));
        for (String s : tmp) {
            oneRes += s; //把这个字母加入oneRes
            combi(digits, i + 1, res, oneRes, map);
            oneRes = oneRes.substring(0, oneRes.length() - 1);//把s从oneRes中删除（这个如果不好理解，可以举个例子23,在纸上走一遍）
        }
    }
}