大廠面試真題詳解：電話号碼的字母組合

給一個不包含0和1的數字字元串，每個數字代表一個字母，請傳回其所有可能的字母組合。

下圖的手機按鍵圖，就表示了每個數字可以代表的字母。

• 以上的答案是按照詞典編撰順序進行輸出的，不過，在做本題時，你也可以任意選擇你喜歡的輸出順序。

線上評測位址：

領扣題庫官網

樣例 1:

輸入: "23"
輸出: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]           

解釋:

'2' 可以是 'a', 'b' 或 'c'

'3' 可以是 'd', 'e' 或 'f'

樣例 2:

輸入: "5"
輸出: ["j", "k", "l"]           

算法：DFS

1. 如果輸入的數字串為空，傳回空清單；
2. 預處理存儲1-9各個數字可以對應的字母；
3. 對數字串進行深度優先搜尋，傳入的參數包括：數字串digits、目前的位置index、目前存入的字元串current、儲存答案的字元串清單result、數字字母映射的字元串數組phone；

• 目前位置達到數字串末尾即達到邊界，将current添加到result，回溯；
• 對index位置的數字通過phone找出可以選用的每個字母，分别遞歸調用dfs；
• 遞歸步進為：index+1， current+選用的字母；

複雜度分析

• 時間複雜度：O(4^n), n為數字串長度
  • 每個數字都有3-4個可對應的字母
• 空間複雜度：O(4^n),n為數字串長度
  • 對于用來儲存答案的清單，最多有4^n種組合

public class Solution {
        /**
         * @param digits: A digital string
         * @return: all posible letter combinations
         */
    
        public static final HashMap<Integer, String> PHONE = new HashMap<Integer, String>() {
            {
                put(0, ""); put(1, ""); put(2, "abc"); put(3, "def"); put(4, "ghi"); 
                put(5, "jkl"); put(6, "mno"); put(7, "pqrs"); put(8, "tuv"); put(9, "wxyz"); 
            }
        };
    
        public List<String> letterCombinations(String digits) {
            List<String> result = new ArrayList<>();
            if (digits.length() == 0) {
                return result;
            }
            dfs(0, "", digits, PHONE, result);
            return result;
        }
    
        private void dfs(int index, String current, String digits, HashMap<Integer, String> PHONE, List<String> result) {
            if (index == digits.length()) {
                result.add(current);
                return;
            }
    
            int d = digits.charAt(index) - '0';
            for (char c : PHONE.get(d).toCharArray()) {
                dfs(index + 1, current + c, digits, PHONE, result);
            }
        }
    }           

更多題解參考：

九章官網solution