17.电话号码的字母组合

题目链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

难度：中等

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

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

image.png

示例:

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

解法一：普通的循环(类似于建树的BFS广度优先搜索，层序遍历)

首先建立手机按键与字符的对应关系，利用Map存储。
我们可以利用遍历digits的每一个字符，依次把当前数字对应的字符串添加到最终的list集合。
每一拿到一个数字按键，拿到按键对应的字符串s，
将当前的list集合和字符串按照笛卡尔积的形式拼接，组合形成新的list。
然后将list返回，进行下一个按键的拼接。
循环结束，返回结果字符串集合。

缺点：时间复杂度为O(n^3)
时间复杂度较高，完成leetcode上面的测试需要7ms。

代码：

    public List<String> addLetter(List<String> list, String s) {
        List<String> newList = new ArrayList<String>();
        for (int j = 0; j < list.size(); j++) {
            for (int i = 0; i < s.length(); i++) {
                newList.add(list.get(j) + s.charAt(i));
            }
        }
        return newList;
    }

    public List<String> letterCombinations(String digits) {
        HashMap<String, String> map = new HashMap<>();
        map.put("2", "abc");
        map.put("3", "def");
        map.put("4", "ghi");
        map.put("5", "jkl");
        map.put("6", "mno");
        map.put("7", "pqrs");
        map.put("8", "tuv");
        map.put("9", "wxyz");
        List<String> result = new ArrayList<>();

        if (digits.length() == 0) {
            return result;
        }
        result.add("");
        for (int i = 0; i < digits.length(); i++) {
            result = addLetter(result, map.get(String.valueOf(digits.charAt(i))));
        }

        return result;
    }

解法二：回溯法(类似于建树的DFS深度优先搜索，深度搜索)

首先建立手机按键与字符的对应关系，利用Map存储。
我们先建立一个空字符串letter,来临时存储组合的结果字符串
我们利用递归，拿出digits中的第一个按键对应的字符串，
然后遍历字符串中的每一个字符，与当前的字符串letter连接，
连接后，我们直接递归去找下一个按键，依次拼接
最终，当没有新的按键输入，那么当前的字符串letter就是最终字符串，（这也是递归结束的条件，递归的出口）
将其保存到最终的集合result中，再依次递归
退出递归后，得到的集合result就是最终结果。

时间复杂度：表面看上去类似于 O(n)。但是如果细究的话肯定不止O(n)。

Leetcode测试案例，运行时间只需要1ms

代码：

    Map<String, String> phoneMap = 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");
        }
    };

    List<String> result = new ArrayList<>();

    public void addLetter2(String letter, String nextLetter) {
        if (nextLetter.length() == 0) {
            result.add(letter);
        } else {
            String digit = String.valueOf(nextLetter.charAt(0));
            String letters = phoneMap.get(digit);

            for (int i = 0; i < letters.length(); i++) {
                String c = String.valueOf(letters.charAt(i));
                addLetter2(letter + c, nextLetter.substring(1));
            }
        }
    }

    public List<String> letterCombinations2(String digits) {
        if (digits.length() != 0)
            addLetter2("", digits);
        return result;
    }