O******i
发帖数: 269 | 1 要是被要求白板写trie的code怎么写？比如输入手机数字键，蹦出一系列匹配的单词，
比如2键上有abc三个字母。 |
r****r
发帖数: 37 | |
n*******w
发帖数: 687 | 3 这是两个小问题吧。
先产生permutation，再去dictionary里边查。后者可以用trie存储字典。比较适合面
试白板的是前一部分。
【在 O******i 的大作中提到】
: 要是被要求白板写trie的code怎么写？比如输入手机数字键，蹦出一系列匹配的单词，
: 比如2键上有abc三个字母。
|
k****n
发帖数: 369 | 4 依赖于数据结构的算法，尤其是trie这种东西，关键是把类的数据想好
然后把接口函数设计好，然后问面试官需要填哪个就写哪个
全写下来是不可能的，也没那么大白板
【在 O******i 的大作中提到】
: 要是被要求白板写trie的code怎么写？比如输入手机数字键，蹦出一系列匹配的单词，
: 比如2键上有abc三个字母。
|
A*****i
发帖数: 3587 | 5 知道一种数据结构，算法你自己完成吧
typedef struct node{
node * next;
int word[26];
}trieNode; |
f*******t
发帖数: 7549 | 6 struct Trie
{
Trie();
~Trie();
Trie *children[26];
bool isEnd;
};
Trie::Trie()
{
for(int i = 0; i < 26; i++)
children[i] = NULL;
isEnd = false;
}
Trie::~Trie()
{
for(int i = 0; i < 26; i++) {
if(children[i]) {
delete children[i];
children[i] = NULL;
}
}
}
void TrieInsert(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid line\n");
return;
}
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index] == NULL) {
cur->children[index] = new Trie();
}
cur = cur->children[index];
str++;
}
if(cur != root)
cur->isEnd = true;
}
int TrieSearch(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid string!\n");
return ENTRYNOTFOUND;
}
printf("Looking for word %s\n", str);
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index]) {
cur = cur->children[index];
str++;
}
else
return ENTRYNOTFOUND;
}
if(cur != root && cur->isEnd)
return ENTRYFOUND;
else
return NOTCOMPLETE;
} |
