今天的算法题是:Compute all mnemonics for a phone number,从一个手机号码得到所有可能的字符组合。

 

如上图所示,是一个我们常见的手机拨号界面,每个按钮都代表了一串字符含义,比如按钮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)。