[LeetCode]--17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

方法一：递归调用

public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<String>();
        String[] map = new String[10];
        map[0] = "";
        map[1] = "";
        map[2] = "abc";
        map[3] = "def";
        map[4] = "ghi";
        map[5] = "jkl";
        map[6] = "mno";
        map[7] = "pqrs";
        map[8] = "tuv";
        map[9] = "wxyz";
        char[] middleTemp = new char[digits.length()];
        dfsGetStr(digits, 0, middleTemp, map, result);
        return result;
    }

    private void dfsGetStr(String digits, int i, char[] middleTemp,
            String[] map, List<String> result) {
        if (i == digits.length()) {
            result.add(new String(middleTemp));
            return;
        }
        char strChar = digits.charAt(i);
        for (int j = 0; j < map[strChar - '0'].length(); j++) {
            middleTemp[i] = map[strChar - '0'].charAt(j);
            dfsGetStr(digits, i + 1, middleTemp, map, result);
        }
    }

方法二：

public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<String>();
        if (digits.isEmpty())
            return result;
        String[] map = new String[10];
        map[0] = "";
        map[1] = "";
        map[2] = "abc";
        map[3] = "def";
        map[4] = "ghi";
        map[5] = "jkl";
        map[6] = "mno";
        map[7] = "pqrs";
        map[8] = "tuv";
        map[9] = "wxyz";
        int len = digits.length();
        int[] number = new int[len];

        int k = len - 1;
        while (k >= 0) {
            k = len - 1;
            char[] charTemp = new char[len];
            for (int i = 0; i < len; i++) {
                charTemp[i] = map[digits.charAt(i) - '0'].charAt(number[i]);
            }
            result.add(new String(charTemp));
            while (k >= 0) {
                if (number[k] < (map[digits.charAt(k) - '0'].length() - 1)) {
                    number[k]++;
                    break;
                } else {
                    number[k] = 0;
                    k--;
                }
            }
        }

        return result;
    }