CONY的世界

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.

這題我的作法主要是data type要慎選吧，首先是table 的key 是 Character而不要用int，因為這樣可以少掉Character.getNumericValue(c)的動作

 然後是value 用String[] 因為畢竟是fixed-size array 是可以不用arraylist的

處理開頭也要注意，因為一開始是沒有的previous，所以要額外判斷然後直接把String[] 轉成List 然後塞到 result 去 

class Solution {
    public List<String> letterCombinations(String digits) {
        HashMap<Character, String[]> table = new HashMap();
        table.put('2',new String[]{"a","b","c"});
        table.put('3',new String[]{"d","e","f"});
        table.put('4',new String[]{"g","h","i"});
        table.put('5',new String[]{"j","k","l"});
        table.put('6',new String[]{"m","n","o"});
        table.put('7',new String[]{"p","q","r","s"});
        table.put('8',new String[]{"t","u","v"});
        table.put('9',new String[]{"w","x","y","z"});
        table.put('0',new String[]{" "});
        return (digits.length()>0)?nthDigitCombination(new ArrayList<String>(), digits, table):new ArrayList<String>();
    }
    public List<String> nthDigitCombination(List<String> previous, String digits, HashMap<Character, String[]> table){
        List<String> result = new ArrayList<String>();
        if(previous.size() == 0) result = Arrays.asList(table.getOrDefault(digits.charAt(0),new String[]{""}));
        else {
            for(String orig : previous) {
                for(String add: table.getOrDefault(digits.charAt(0),new String[]{""})){
                    result.add(orig+add);
                }        
            }
        }
        return (digits.length()>1)?nthDigitCombination(result, digits.substring(1), table):result;
    }
}

 不過後來看到更好的做法不用建hashmap，直接用到之前學的用 asii code 讓 char 轉 int 的方式

 搭配是一個 numerical digit 換一個 alphbetic digit 的一換一特性，用 linkedlist 不斷替換（remove, add () ) 出答案，很漂亮的解法

這題我跟參考解法用的方法都是某種BFS，因為就是先loop 過第一個bit 再來第二個，持續下去

不過討論中也有人用DFS，不過因為都要跑出所有組合，所以複雜度都是一樣的

class Solution {
    public List<String> letterCombinations(String digits) {
        String[] arr = new String[]{"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        LinkedList<String> result = new LinkedList<String>();
        for(int index=0; index<digits.length(); index++){
            while(result.peek()==null || result.peek().length()==index) {
                String orig = (result.peek()==null)?new String():result.remove();
                for(char c : arr[digits.charAt(index) - '0'].toCharArray())
                    result.add(orig+c);
            }
        }
        return result;
    }
}