首页 > 代码库 > 编程之美之电话号码对应英语单词

编程之美之电话号码对应英语单词

题目一:根据电话上字母和数字的对应关系,用一个有意义的单词来表述一个电话号码,如用computer表示26678837

题目二:反过来,给定一个电话号码,是否可以用一个单词来表示呢?怎样表示最快呢?显然不是所有的电话号码都可以对应到单词上去

首先来看看leetcode上一个类似的题目:

Letter Combinations of a Phone Number

 

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

思路:用递归实现比较简单,首先建立一个hash表,然后对每一个数字,深度搜索可能的取值,当每个数字都取一个值之后,就得到了一个结果,具体如下:

class Solution {
public:
    void letterCombinations(string& digits,int index,string* map,string words,vector<string>& res)
    {
    	if(index == digits.size())//得到一个结果
    	{
    		res.push_back(words);
    		return;
    	}
    	int i;
    	for(i = 0; i < map[digits[index] - '0'].size();++i)//取第index个数字上的每一个字符,进行深度递归
    	{
    		letterCombinations(digits,index + 1,map,words+map[digits[index] - '0'][i],res);
    	}
    }
    vector<string> letterCombinations(string digits) {
    	string map[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//数字和字母的对应关系
    	vector<string> res;
    	letterCombinations(digits,0,map,"",res);
    	return res;
    }
};
根据这个题目,上面的两个问题就比较简单了,正如编程之美上说的:对于问题二,我们找出该电话所有可能组合,然后去匹配字典,判断是否有答案。当然,如果查询的次数比较多,可直接把字典里的所有单词都按照这种转化关系映射成数字,并保存到文件中,然后对这个电话号码按照查表的方式来得到结果。