问道题，找到电话按键能组成的所有的词 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问道题，找到电话按键能组成的所有的词

问道题，找到电话按键能组成的所有的词# JobHunting - 待字闺中

K*n2012-11-12 08:11

1 楼

Suppose we have a dictionary of words. Given a phone number, determine all t
he words that can be made from it using the letters corresponding to each di
git on a 12-key phone keypad.
这是不是典型的prefix tree问题，除此之外有没有其他解法？谢谢！

p*e2012-11-12 08:11

2 楼

这题不是trie啊，暴力搞就行了啊

t
di

【在 K*********n 的大作中提到】

: Suppose we have a dictionary of words. Given a phone number, determine all t
: he words that can be made from it using the letters corresponding to each di
: git on a 12-key phone keypad.
: 这是不是典型的prefix tree问题，除此之外有没有其他解法？谢谢！

K*n2012-11-12 08:11

3 楼

那得多暴力啊……recursion？

【在 p*****e 的大作中提到】

: 这题不是trie啊，暴力搞就行了啊
:
: t
: di

p*22012-11-12 08:11

4 楼

dfs就行了吧？

K*n2012-11-12 08:11

5 楼

哦，我看错题了……是给定一个电话号码……我还以为是要算这个键盘能够产生的所有
可能的词……

【在 K*********n 的大作中提到】

: 那得多暴力啊……recursion？

K*n2012-11-12 08:11

6 楼

是不是一棵树，每一个结点有三个孩子，一共7层，不考虑0和1的情况。然后dfs，看能
不能找到？好像也不是dfs啊，就是沿一条路找到底就行了吧。

【在 p*****2 的大作中提到】

: dfs就行了吧？

p*22012-11-12 08:11

7 楼

基本就这样吧。为什么不是dfs呢？

【在 K*********n 的大作中提到】

: 是不是一棵树，每一个结点有三个孩子，一共7层，不考虑0和1的情况。然后dfs，看能
: 不能找到？好像也不是dfs啊，就是沿一条路找到底就行了吧。

K*n2012-11-12 08:11

8 楼

嗯，是吧。不是从第一个数字开始的词大概也算。

【在 p*****2 的大作中提到】

:
: 基本就这样吧。为什么不是dfs呢？

l*82012-11-12 08:11

9 楼

O(n), n = number of words in dict

★ 发自iPhone App: ChineseWeb 7.7

【在 K*********n 的大作中提到】

: 那得多暴力啊……recursion？

b*u2012-11-12 08:11

10 楼

这样的话即使只有一个键也要遍历整个dict

【在 l*******8 的大作中提到】

: O(n), n = number of words in dict
:
: ★ 发自iPhone App: ChineseWeb 7.7

t*a2012-11-12 08:11

11 楼

因为phone number已经给定，这就相当于给定了一组条件：
1. 单词长度为len(phone number)
2. 单词中位置为i的字符属于集合S_i, 比如{A,B,C}
如果单词表中单词个数为m，且已经对长度以及每个位置的字母建立了索引，那么本题
的复杂度，平均情况为O(log(m)*log(n+1))，其中log(m)是检索每个位置的速度，log(
n+1)是考虑到每次过滤都将结果筛成原来的一小部分。
我对log(n+1)这个写法不是很确信:) 请高手来指点我，谢谢。

w*o2012-11-12 08:11

12 楼

因为字典已经给定，就不需要对字典做预处理，可以假设为HashMap，在字典里找词应
该是O（1）吧。我觉得这题的重点是要找所有valid的10个字符的排列。

e*e2012-11-12 08:11

13 楼

I'm with you. I don't think prefix tree(trie) is needed. Here is my code.
String[] pad = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs
", "tuv", "wxyz"};
List words = new ArrayList();
Set dict = // Preloaded.
public void determineWord(String word, String remaining) {
if ( "".equals( remaining ) ) {
if(dict.contains( word )
words.add( word );
return;
}

int digit = remaining.charAt(0)-'0';
String letters = pad[digit];
for ( int i = 0; i < letters.length(); i++ )
determineWord( word + letters.charAt( i ), remaining.substring(
1 ) );
}
client code:
determineWord( "", "3456789" );

【在 w***o 的大作中提到】

: 因为字典已经给定，就不需要对字典做预处理，可以假设为HashMap，在字典里找词应
: 该是O（1）吧。我觉得这题的重点是要找所有valid的10个字符的排列。

c*t2012-11-12 08:11

14 楼

赞，是不是字符的permutation问题一般都是用dfs+backtracking来解决？

pqrs

【在 e****e 的大作中提到】

: I'm with you. I don't think prefix tree(trie) is needed. Here is my code.
: String[] pad = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs
: ", "tuv", "wxyz"};
: List words = new ArrayList();
: Set dict = // Preloaded.
: public void determineWord(String word, String remaining) {
: if ( "".equals( remaining ) ) {
: if(dict.contains( word )
: words.add( word );
: return;

e*e2012-11-12 08:11

15 楼

Not sure. recursion is more intuitive to me when solving 字符的permutation问
题. Thanks.

【在 c********t 的大作中提到】

: 赞，是不是字符的permutation问题一般都是用dfs+backtracking来解决？
:
: pqrs