17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

Input: "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.

My Solutions:

先把电话号码盘存入String[] disc。0 --> 空格，1 --> 空string，2 --> "abc", ...

和combination类似，temp加入list的条件是temp长度和digits长度相同。

class Solution {

    private final String[] KEYS = {" ","", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        ArrayList<String> list = new ArrayList<String>();
        if (digits.length() <= 0) return list;
        dfs(list, new StringBuilder(), digits, 0);
        return list;
    }
    
    public void dfs(List<String> list, StringBuilder temp, String digits, int index) {
        if (temp.length() == digits.length()) { // 长度符合
            list.add(temp.toString());
            return;
        }
        
        String letters = KEYS[digits.charAt(index) - '0'];
        //注意此处i=0，因为disc里每个数字index对应有3-4个char，每个都需要循环一遍
        for (int i = 0; i < letters.length(); i++) {
            temp.append(letters.charAt(i));
            dfs(list, temp, digits, index + 1);
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

类似的，也可以用HashMap储存键盘。index也可以省略掉，因为可以用 letters记录每个数字对应的几个字母，用letters.toCharArray() 遍历，通过每次dfs时减少digits的长度，每一次letters取digits第一个数字上的字母。

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.length() == 0) return result;
        
        Map<Character, String> disc = new HashMap<>();
        disc.put('2', "abc");
        disc.put('3', "def");
        disc.put('4', "ghi");
        disc.put('5', "jkl");
        disc.put('6', "mno");
        disc.put('7', "pqrs");
        disc.put('8', "tuv");
        disc.put('9', "wxyz");
        
        dfs(disc, new StringBuilder(), digits, result);
        return result;
    }
    
    public void dfs(Map<Character, String> disc, StringBuilder sb, String digits, List<String> result)
    {
        if (digits.length() == 0) {
            result.add(sb.toString());
            return;
        }
        String letters = disc.get(digits.charAt(0));
        for (char c : letters.toCharArray()) {
            sb.append(c);
            dfs(disc, sb, digits.substring(1), result);
            sb.setLength(sb.length() - 1);
        }
    }
}

Time & Space: O(3^M * 4^N), M是有3个字母的按键数量，N是有4个字母的按键数量