5/7 演算法題詳解：Compute all mnemonics for a phone number 從一個手機號碼得到所有可能的字元組合

01-25

本視頻來自於北美CS刷題神器BitTiger Pro。

如上圖所示，是一個我們常見的手機撥號界面，每個按鈕都代表了一串字元含義，比如按鈕2就代表了A、B和C三個字元，按鈕9代表了W、X、Y和Z四個字元。那麼問題來了，如果給了一串字元串形式的電話號碼，我們就需要返回所有可能代表的字元排列組合。比如說「2276696」可以代表的含義是「ACRONYM」，也可以代表「ABPOMZN」，而且我們列舉的這兩種還只是簡單舉個例子，還有大量其他組合，那我們就要考慮如何實現了。

解法一：蠻力法

給了一串電話號碼，我們輕而易舉的就能想到的蠻力的方法。比方說如果這個數字是「2276696」，那麼它的範圍可能是『A-C』、『A-C』、『P-S』、『M-O』、『M-O』、『W-Z』、『M-O』。我們可以使用7重循環，來覆蓋所有的可能的組合。

解法二：遞歸法

蠻力法有很多問題，首先，說我們不能確定輸入的字元串長度，如果輸入長度有8位，那我們就需要修改代碼以便實現8重循環。其次，事實上，每一重循環的代碼都是高度類似的，以至於我們不得不寫下大量重複代碼。所以基於這兩個特點，很明顯我們會使用遞歸的方式來解決這個問題。

首先定義一個phoneMnemonic的方法，用來調用遞歸方法phoneMnemonicHelper。輸入是從鍵盤輸入的字元串phoneNumber，輸出是一個字元串列表，包含輸入phoneNumber對應的所有可能的組合。方法內首先定義了一個字元數組變數，partialMnemonic，長度和phoneNumber一致，用來存放生成的局部結果。其次定義一個字元串列表變數mnemonics，這個變數存放生成所有結果。然後調用遞歸方法phoneMnemonicHelper，開始遞歸調用。最後返回mnemonics的值。具體代碼如下圖所示：

下面就是核心的遞歸部分了。首先我們看一下遞歸方法的輸入部分，第一個參數是字元串phoneNumber，第二個是一個整數digit，用來定位遞歸調用到哪一步了，第三個參數是partialMnemonic，用來存放局部的結果，第四個是mnemonics，用來存放最終結果。需要注意一下，還定義了一個靜態字元串數組變數MAPPING，存放每個按鈕可能代表的字元含義，而且每個字元串對應的順序與鍵盤上的數字一直，比如第0個字元串「0」，對應按鈕是鍵盤上的0，第3個字元串「DEF」對應按鈕是鍵盤上的3。

在遞歸的方法中，我們需要定義一個遞歸結束（邊界條件）的情況以便退出遞歸，本方法中定義的就是當自增長的變數digit等於字元串phoneNumber的長度的時候。就將局部結果partialMnemonic構造成字元串，添加到最終結果字元串列表mnemonics中。

在遞歸中，我們藉助for循環不斷更新partialMnemonic對應位置的字元值，每到達一次邊界條件，就返回一個字元串。代碼如下圖所示：

讓我們分析一下這個演算法的性能，首先是時間複雜度，因為鍵盤按鍵每個按鈕最多有4種可能的字元，這樣我們就有種組合，對於每個組合事實上都要進行一次深拷貝（deep

copy），這樣我們的時間複雜度就是O(n)。其次是空間複雜度，由於我們有種組合，而且每一個字元數組都需要被存儲，所以空間複雜度也是O(n)。

本視頻來自於北美CS刷題神器BitTiger Pro。

每月更新的BitTiger Pro是一個覆蓋了CS和數據科學方向最新高頻面試題的精講視頻庫。訂閱後，你可以在Code Evaluation System親自練習這道題。