給定一個僅包含數字2-9的字符串，返回所有它能表示的字母組合。答案可以按任意順序返回。給出數字到字母的映射如下（與電話按鍵相同）。注意1不對應任何字母。
示例 1：
輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
示例 3：
輸入：digits = "2"
輸出：["a","b","c"]
提示：
0<=digits.length<=4
digits[i]是範圍['2','9']的一個數字。
每一個數字對應3到4個字符，我們以示例一為例畫個圖來看一下
我們看到實際上就是一顆n叉樹，除了葉子節點外，每個節點都有3到4個子節點。對於二叉樹的BFS遍歷如下圖所示，也就是一行一行的訪問
二叉樹的BFS遍歷代碼如下
publicvoidlevelOrder(TreeNodetree){//鍊表，這裡我們可以把它看做隊列LinkedList<TreeNode>list=newLinkedList<>();list.add(tree);//相當於把數據加入到隊列尾部while(!list.isEmpty()){//poll方法相當於移除隊列頭部的元素TreeNodenode=list.poll();//訪問當前節點System.out.println(node.val);//遍歷當前節點的左子節點和右子節點if(node.left!=null)list.add(node.left);if(node.right!=null)list.add(node.right);}}因為最多有兩個子節點所以是二叉樹，如果最多有n個子節點我們可以稱它為n叉樹，那麼n叉樹的子節點比較多，我們不可能一次性全部寫完，可以使用for循環來遍歷，代碼如下
publicvoidlevelOrder(TreeNodetree){//鍊表，這裡我們可以把它看做隊列LinkedList<TreeNode>list=newLinkedList<>();list.add(tree);//相當於把數據加入到隊列尾部while(!list.isEmpty()){//poll方法相當於移除隊列頭部的元素TreeNodenode=list.poll();//訪問當前節點System.out.println(node.val);//遍歷當前節點的所有子節點for(inti=0;i<node.child.count;i++){list.add(node.child[i]);}}}搞懂了上面的代碼，那麼這題的答案就比較簡單了。實際上這題給的並不是一棵樹，這棵樹只是我們想象的，那我們怎麼確定走到葉子節點了呢，實際上很簡單，如果有n個數字，那麼葉子節點字符串的長度就應該是n。來看下代碼
//BFSpublicList<String>letterCombinations(Stringdigits){LinkedList<String>res=newLinkedList<>();//空判斷if(digits==null||digits.isEmpty())returnres;char[][]tab={{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};res.add("");while(res.peek().length()!=digits.length()){Stringremove=res.poll();//出隊char[]chars=tab[digits.charAt(remove.length())-'2'];//相當於當前節點的所有子節點for(inti=0;i<chars.length;i++){res.add(remove+chars[i]);//入隊}}returnres;}對於一棵樹的遍歷，除了BFS以外我們很自然的會想到DFS，這裡我們可以把它看做是一棵樹的前序遍歷。網上說這種是回溯算法，實際上這裡往回走的時候並不需要撤銷選擇，因為字符串每次都會生成一個新的對象，所以並不會造成其他分支的污染，關於回溯算法具體可以看下450，什麼叫回溯算法，一看就會，一寫就廢。我們來看下這題的代碼
publicList<String>letterCombinations(Stringdigits){List<String>res=newArrayList<>();if(digits==null||digits.isEmpty())returnres;char[][]tab={{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};dfs(res,0,digits,tab,"");returnres;}/***@paramres*@paramindex表示訪問到第幾個數字了，也可以認為訪問到樹的第幾層了*@paramdigits*@paramtab*@parampath從根節點到葉子結點的路徑*/privatevoiddfs(List<String>res,intindex,Stringdigits,char[][]tab,Stringpath){//到葉子節點了，就把這條路徑選擇的字符添加到res中if(path.length()==digits.length()){res.add(path);return;}char[]chars=tab[digits.charAt(index)-'2'];//訪問當前節點的所有子節點for(inti=0;i<chars.length;i++){dfs(res,index+1,digits,tab,path+chars[i]);//因為字符串是創建了一個新的對象，所以這裡不需要撤銷}}截止到目前我已經寫了600多道算法題了，為了方便大家閱讀，我把部分算法題整理成了pdf文檔，目前有1000多頁，大家可以在下面公眾號「數據結構和算法」中回復關鍵字「pdf」即可獲取下載鏈接。
想學習算法，還可以長按下面二維碼加我微信，我給你拉到算法學習群，在工作中或者學習中遇到不會的問題都可以在群里討論。
留言列表