Problem: 17. 電話號碼的字母組合

題目描述

思路

題目給定一串數字，要求我們找出所有可能的字母組合，即我們可以窮舉出所有可能的結果，而涉及到窮舉我們自然可以想到利用回溯來解決問題，在本題目中我們選擇給定字符串digits中的每一個字符作為決策階段，具體的：

1.我們先創建一個哈希表將數字與其對應的字符存入（數字作為鍵，所有的字符作為值）
2.編寫，并調用回溯函數，當決策階段等于digits的長度時，將當前的決策路徑添加到結果集合中，否則從digits字符串的第一個字符開始回溯調用！

解題方法

1.創建結果集合result，若當digits為空時，返回空集合；
2.創建一個String類型的數組mappings作為哈希表，索引從0-9，用于存儲數字與其字符的對應關系，其中數字索引作為鍵，所有的字符作為值；
3.創建一個char類型的數組，數組長度為digits字符串的長度，作為回溯過程中的決策路徑；
4.編寫并調用回溯函數，參數列表為（String[] mappings, String digits, int k, char[] path）,其中由參數mappings 與digits決定參數列表，k表示決策階段，path表示決策路徑

4.1若k等于digits的長度時，表示找到一個字母組合，則將其添加到結果集合result中，
4.2先得到當前決策階段的digits中的數字字符，再通過我們創建的哈希表mappins找出該數字字符對應的所有字母字符
4.3以當前的數字字符對應得所有字母字符開始，遍歷所有得字母字符并開始回溯調用

注意：在上述解題方法中我們沒有顯示地在回溯調用后將當前的決策階段狀態還原（回溯的本質就是一個多狀態轉移）但這并不表示我們沒有實現該操作，而是因為：我們定義的決策階段是一個char類型的數組，再回溯遞歸的調用過程中會將原來索引位置上的值給覆蓋掉，以達到恢復當前決策階段的操作

復雜度

時間復雜度:

最壞時間復雜度：$O(3^m\times 4^n)$,其中m表示選擇對應只有三個字母的數字的個數，n表示對應四個字母的個數

空間復雜度:

$O(n+m)$

Code

class Solution {//Result listprivate List<String> result = new ArrayList<>();/*** Get the all possible combinations** @param digits The combination given by topic* @return List<String>*/public List<String> letterCombinations(String digits) {if (digits.length() == 0) {return Collections.emptyList();}//Create the reflectionString[] mappings = new String[10];mappings[2] = "abc";mappings[3] = "def";mappings[4] = "ghi";mappings[5] = "jkl";mappings[6] = "mno";mappings[7] = "pqrs";mappings[8] = "tuv";mappings[9] = "wxyz";//Decision pathchar[] path = new char[digits.length()];backtrack(mappings, digits,0, path);return result;}/*** Use backtracking to find all possible combinations** @param mappings Mapping between letters and numbers* @param digits   Combination of numbers given by topic* @param k        Decision stage* @param path     Decision path*/private void backtrack(String[] mappings, String digits, int k, char[] path) {//End conditionif (k == digits.length()) {result.add(new String(path));return;}String mapping = mappings[digits.charAt(k) - '0'];for (int i = 0; i < mapping.length(); ++i) {path[k] = mapping.charAt(i);backtrack(mappings, digits, k + 1, path);}}
}