1. 就是深搜。深搜三原则：终止条件，当下操作，回退。

2. 写完发现，这题早就做过了。

代码如下： 

class Solution {

    public List<String> letterCombinations(String digits) {

        if(null==digits || digits.equals("")){

            return new ArrayList<String>();

        }

        Map<Character, String> map = new HashMap<Character, String>();

        // map.put('1',)

        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<String>();

        StringBuffer sb = new StringBuffer("");

        letterCombinationsHelp(result, map, digits, 0, sb);

        return result;

    }

    void letterCombinationsHelp(List<String> result, Map<Character, String> map, String digits,int index, StringBuffer sb  ){

        if(index == digits.length() ){

            result.add(sb.toString());

            return;

        }

        String letterList = map.get(digits.charAt(index));

        for(int i = 0; i < letterList.length(); i++){

            sb.append(letterList.charAt(i));

            letterCombinationsHelp(result, map, digits, index+1, sb);

            sb.deleteCharAt(index);

        }

    }

}