每天一道算法题

LeetCode第17题：电话号码的字母组合

这道题首先一看题目，号码数目不固定，那么肯定不能用循环，否则会嵌套很多层，这种题首先应该想到的是递归方案，能意识到应该用递归解法就很容易想出来了。

public static List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return new ArrayList<>();
        }
        Map<Character, List<String>> phoneMap = new HashMap<Character, List<String>>() {{
            put('2', Arrays.asList("a", "b", "c"));
            put('3', Arrays.asList("d", "e", "f"));
            put('4', Arrays.asList("g", "h", "i"));
            put('5', Arrays.asList("j", "k", "l"));
            put('6', Arrays.asList("m", "n", "o"));
            put('7', Arrays.asList("p", "q", "r", "s"));
            put('8', Arrays.asList("t", "u", "v"));
            put('9', Arrays.asList("w", "x", "y", "z"));
        }};


        return getStrings(phoneMap, digits);
    }

    /**
     * 递归拼接，每次返回的都是当前第一位字符与剩下的结果乘出来的并集
     * @param phoneMap
     * @param digits
     * @return
     */
    public static List<String> getStrings(Map<Character, List<String>> phoneMap, String digits) {
        if (digits.length() == 1) {
            return new ArrayList<>(phoneMap.get(digits.charAt(0)));
        }
        List<String> first = phoneMap.get(digits.charAt(0));
        List<String> subAns = letterCombinations(digits.substring(1, digits.length()));
        List<String> ans = new ArrayList<>();
        for (String subAn : subAns) {
            for (String s : first) {
                ans.add(s + subAn);
            }
        }
        return ans;
    }