3.2　电话号码对应英语单词

电话的号码盘一般可以用于输入字母。如用2可以输入A、B、C，用3可以输入D、E、F等。如图3-1所示：

图3-1　手机按键示意图

对于号码5869872，可以依次输出其代表的所有字母组合。如：JTMWTPA、JTMWTPB……

1．您是否可以根据这样的对应关系设计一个程序，尽可能快地从这些字母组合中找到一个有意义的单词来表述一个电话号码呢？如：可以用单词“computer”来描述号码26678837。

2．对于一个电话号码，是否可以用一个单词来代表呢？怎样才是最快的方法呢？显然，肯定不是所有的电话号码都能够对应到单词上去。但是根据问题1的解答，思路相对就会比较清晰。

分析与解法

对于题目1，不妨掏出手机或寻找身边的电话来进行研究，相信我们很快就能够找出规律。可以发现除了0、1之外，其他数字上都最少有3个字符，其中7、9上有4个字符，我们假设0、1输出的是空字符。

首先将问题简单化。若电话号码只有一位数，比如说4，那么其代表的“单词”为G、H、I，据此可以画出一棵排列树，如图3-2所示：

图3-2　排列树示意图

接着若电话号码升级到两位数（比如42），又将如何呢？分两步走，从左到右，在选择一个第一位数字所代表的字符的基础上，遍历第二位数字所代表的字符，直到遍历完第一位数字代表的所有字符。就拿42来说，4所能代表的字符为（G，H，I），2所能代表的字符为（A，B，C），首先让4代表G，接着遍历2所能代表的所有字符，即可得到GA、GB、GC；然后再让4代表H，再次遍历2所能代表的所有字符，可得到HA、HB、HC；最后让4代表I，那么同理可得到IA、IB、IC。

同样，可以在4所表示的排列树的基础上，进一步画出42所表示的排列树，如图3-3所示：

图3-3　多个数字的排列树示意图

聪明的读者可能已经发现，通过遍历这棵排列树所有叶子节点而得到的所有路径的集合，即为42所能代表的所有“单词”的集合。

那么现在无论电话号码的位数如何升级，相信大家都能够构造出相应的排列树，从而可以简单地通过遍历所有的叶子节点，得到其所代表的“单词”集合。

通过分析，下面要做的就是如何遍历得到一个电话号码所能代表的“单词”集合。

【问题1的解法一】直接循环法

将各个数字所能代表的字符存储在一个二维数组中，其中假设0、1所代表的字符为空字符。

代码清单3-2

并将各个数字所能代表的字符总数记录于另一个数组中：

int total[10]＝{0，0，3，3，3，3，3，4，3，4};

用一个数组存储电话号码：

int number[TelLength]; //TelLength为电话号码的位数

将数字目前所代表的字符在其所能代表的字符集中的位置用一个数组储存起来：

int answer[TelLength]; //TelLength为电话号码的位数，初始化时answer[i]＝0．

举个例子，若Number[0]＝4，即电话号码的第一位为4，若answer[0]＝2，即4目前所代表的字符为：

c[number[0]][answer[0]]＝c[4][2]＝＇I＇。

假设电话号码只有三位，那么可能会有人很快写出3个for循环来。

代码清单3-3

的确，针对3位的电话号码，此3个for循环可以很好地解决问题（n位的电话号码，则需要n个for循环），但是不同地区的电话号码位数不同，而且若是电话号码位数升级了呢？我们就需要修改源代码去增加若干个for循环，这是一件很痛苦的事情，而且也实在体现不出编程之“美”来，其实对程序进行简单修改，即可解决这样的扩展性问题。

代码清单3-4

【问题1的解法二】递归的方法

循环的方法固然简单，如果要求使用递归，又该如何解决呢？其实可以从循环算法中那些被我们批判的n个for循环方法中得到提示，每层的for循环，其实可以看成一个递归函数的调用。

代码清单3-5

其中number[]和answer[]的含义同上，number[]用于存放电话号码，answer[]则用于存放对应数字目前所代表的字符在其所能代表的字符集中的位置，index则说明对电话号码的第几位进行循环，n为电话号码的位数。那么递归的初始调用为RecursiveSearch（number，answer，0，n）。

【问题2的解法一】

利用问题1的算法，把该电话号码所对应的字符全部计算出来，然后去匹配字典，判断是否有答案。

【问题2的解法二】

如果查询的次数较多，可直接把字典里面的所有单词都按照这种转换规则转换为数字，并存到文件中，使之成为另一本数字字典。然后，通过对这个电话号码查表的方式来得到结果。事实上这已经有相应的Web应用出现了，网站服务器中存放着经过转换的数字字典，客户端通过浏览器就可以很方便快捷地进行查询。但若查询的次数较少，比如只在Client查一两次，那么翻译整本数字字典就不值得了。