1. Question

给一个数字字符串，按照电话上各个数字对应的字母，返回该字符串代表的所有可能的字母组合。

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"].

2. Solution（O(3ⁿ)）

考虑特殊情况：

• 空串

2.1 遍历法

依次遍历字符串中的每个数，寻找可能的组合。

public List
         
           letterCombinations( String digits ){        String[] map = { " ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};        int len = digits.length();        LinkedList
          
            res = new LinkedList
           
            ();        if( len<1 )            return res;        res.add("");        for( int i=0; i
           
          
         

2.2 树搜索法

对数字进行解析，相当于遍历一棵树，可以使用数的遍历算法

public List
         
           letterCombinations(String digits) {        List
          
            result = new ArrayList
           
            ();        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 index,             char[] middleStr, String[] map, List
            
              result) {        if(index == digits.length()) {            result.add(new String(middleStr));            return ;        }        char strChar = digits.charAt(index);        for(int i=0; i