2016/09/07 电面

mren 发表于 2016-9-9 11:11
我觉得可以这样，建一个hash表，保存为形式，将字典中的每一个单词映射成一个整数，即a-z分别对于整数的0-2 ...

我**一只，以前地里也没见过这题，当时就能想起来啥就是啥了。
贴出题来，有空的看见的就练练手，万一谁碰到一样的呢，就算幸运了~~

PS ： 我好像说了个 Cache 的想法，他觉得挺好的。因为开始都是两个或三个字母，所以用来当 key
比如 key (RT)  value (RAT, CURT, CART...)
这样每次查找的范围就小了。
不过我没写代码

shuiguo 发表于 2016-9-9 11:11
请问dictionary的size是多少？给的input是什么形式？需要自己建树么？

想了想感觉保证最短还挺难

这个我也可崩溃了，他没说 dictionary 什么结构，我问他，他说我自己选。。
我开始用 String[] 效率不好，后来优化的时候，可以改成 hashmap

shuiguo 发表于 2016-9-9 11:24
请问如何转化为int并且保证car和rac是同一个key？而且还可能车牌是cr，对应的词是car，这种情况怎么办？

转化是这样的
int key = 0;
for(int i = 0; i < str.size(); i++)
    key |= (1<<(lowercase(str[i])-'a'));
比较的时候cr对于的数字和car对于的数字相与等于cr对于的数字即可进行查当前key下的单词

mren 发表于 2016-9-9 11:33
转化是这样的
int key = 0;
for(int i = 0; i < str.size(); i++)

这个无法应对多个相同字母的情况吧

感觉是需要件trie的

houqingniao 发表于 2016-9-10 00:26
感觉是需要件trie的

我的第一反应也是建trie 然后就可以直接找了

提取出字母，做char频统计，然后遍历dictionary，每个word做char频统计，输出包含所有车牌里的字母的最短的那个单词

第二題用 edit distance 可以嗎？

补充内容 (2016-9-24 10:32):
說錯，不是第二題．．．我是指第二個函數．．．

如果建立trie时候，是不是也需要把dictionary里word先sort好再插入trie树，遇到一个新的车牌，提取字母，然后sort后，在trie里查找？遇到重复字母，好像有点麻烦。

pinkdatura 发表于 2016-9-24 13:11
如果建立trie时候，是不是也需要把dictionary里word先sort好再插入trie树，遇到一个新的车牌，提取字母，然 ...

如果要把word sort后再放入trie, 那return前要回复原本在dictionary的order.
一开始建一个sort -> unsort 的HashMap..