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.

思路：

这实际上就是一个求全排列的问题

代码：

　　public List<String> letterCombinations(String digits) {
        
        List<String> l = new ArrayList<>();
        
        Map<Character, String[]> map = new HashMap<Character, String[]>();
        map.put('2',new String[]{"a","b","c"});
        map.put('3',new String[]{"d","e","f"});
        map.put('4',new String[]{"g","h","i"});
        map.put('5',new String[]{"j","k","l"});
        map.put('6',new String[]{"m","n","o"});
        map.put('7',new String[]{"p","q","r","s"});
        map.put('8',new String[]{"t","u","v"});
        map.put('9',new String[]{"w","x","y","z"});
        
        if(digits.trim().equals("")){
            return l;
        }
            
        String[] s1 = map.get(digits.charAt(0));
        
        if(digits.length() > 1){
            String[] s2 = map.get(digits.charAt(1));
            for (int i = 2; i < digits.length(); i++) {
                s1 = combinationTwo(s1,s2);
                s2 = map.get(digits.charAt(i));
            }
            s1 = combinationTwo(s1,s2);
        }
        l.addAll(Arrays.asList(s1));
        return l;
    }
    
    //两两组合
    public String[] combinationTwo(String[] s1,String[] s2){
        
        String[] s = new String[s1.length*s2.length];
        int k = 0;
        for (int i = 0; i < s1.length; i++) {
            for (int j = 0; j < s2.length; j++) {
                String str = s1[i]+s2[j];
                s[k] = str;
                k++;
            }
        }
        return s;
    }