a***u
发帖数: 383 | 1 下午刚面的，面试官是一个华裔abc， 人很nice。
题目是anagram的变种，就是给一个dictionary， 再输入一个word， 让我写个
function去找dictionary里面是否有这个word的anagram。
我先是想到了LC的anagram，就说把每个dictionary 里面的sort 一下然后存个hashmap
。她说行，开始编程。完事后面试官让我试不同的testcase，问复杂度并且，我说O（
nklgk）. 她问能不能更efficent一点。我说用个对每个dictionary的word建立一个int
array，然后统计每个char的出现次数 这样应该是O(nk)。她问有没有别的方法，我就
说可以不用array, 用hashmap 统计（我实在想不到别的办法了）。面试官又问用矩阵
和hashmap的区别和各自优缺点。我胡扯一通，时间到了。听面试官的语气应该还有更
好的解法，希望版上大牛们能指导一下。总体上说面试官人很nice，也没为难我，经常
给提示。 |
z*******o
发帖数: 4773 | 2 字典多大?
给你本牛津字典你也sort然后存个hashmap? |
a***u
发帖数: 383 | 3 字典是常用的email domain
【在 z*******o 的大作中提到】
: 字典多大?
: 给你本牛津字典你也sort然后存个hashmap?
|
s********l
发帖数: 998 | 4 字典肯定要预处理
不然 慢死了~
【在 z*******o 的大作中提到】
: 字典多大?
: 给你本牛津字典你也sort然后存个hashmap?
|
f**********e
发帖数: 288 | 5 先调出， all the anagram of the input word, 然后再找。 |
a***u
发帖数: 383 | 6 good idea～
【在 f**********e 的大作中提到】
: 先调出， all the anagram of the input word, 然后再找。
|
g*****g
发帖数: 34805 | 7 That's slower than OPs approach.
【在 f**********e 的大作中提到】
: 先调出， all the anagram of the input word, 然后再找。
|
b*****m
发帖数: 77 | 8 造一个Trie, 先sort字典每个词，然后按sorted word的字母顺序放进trie，但是在最
后一个node 里面用一个list放进原来的词.这个list里面就是需要的所有anagram |
m********g
发帖数: 1489 | 9 for each word in the dictionary
insert coded string to hash_map //sth like abbcdce --> a1b2c2d1e1
look up the coded(input) in the hash_map |
n******n
发帖数: 12088 | 10 矩阵和hash的区别？这完全两回事啊。
hashmap
int
【在 a***u 的大作中提到】
: 下午刚面的，面试官是一个华裔abc， 人很nice。
: 题目是anagram的变种，就是给一个dictionary， 再输入一个word， 让我写个
: function去找dictionary里面是否有这个word的anagram。
: 我先是想到了LC的anagram，就说把每个dictionary 里面的sort 一下然后存个hashmap
: 。她说行，开始编程。完事后面试官让我试不同的testcase，问复杂度并且，我说O（
: nklgk）. 她问能不能更efficent一点。我说用个对每个dictionary的word建立一个int
: array，然后统计每个char的出现次数 这样应该是O(nk)。她问有没有别的方法，我就
: 说可以不用array, 用hashmap 统计（我实在想不到别的办法了）。面试官又问用矩阵
: 和hashmap的区别和各自优缺点。我胡扯一通，时间到了。听面试官的语气应该还有更
: 好的解法，希望版上大牛们能指导一下。总体上说面试官人很nice，也没为难我，经常
|
|
|
d**********6
发帖数: 4434 | 11 dictionary的预处理，用你说的每个char出现频率的int数组做key，搞一个巨大的
hashmap
这样就是统计一下给定word的字频，O(n)，找anagram是O(1) |
T*****u
发帖数: 7103 | 12 sort the word and save in a tree? |
w*****1
发帖数: 6807 | 13 刚自己做了下，想法：字典肯定不能动，只能在给出的word上下功夫
1.把给出的word的所有anagrams存一个vector anagrams，用next_
permutation
2.再找每个anagrams里的词是不是在dict里面
时间复杂度应该是factorial(n)，因为所有permutations有factorial(n)个，这里n
是给出word的长度。
代码如下，已测试，板上大牛有更好想法还希望指出，我好改正
-------------------------------------------------------
vector allPermutations(string &s) {
vector result;
if (s.empty()) return result;
sort(s.begin(), s.end());
result.push_back(s);
while (next_permutation(s.begin(), s.end())) {
result.push_back(s);
}
return result;
}
bool isAnagramInDict(string word, unordered_set dict) {
vector anagrams = allPermutations(word);
for (auto s : anagrams) {
if (dict.find(s) != dict.end()) return true;
}
return false;
} |
w********m
发帖数: 1137 | 14 permutation的改写吧。发现anagram立即退出，最坏复杂度k!
hashmap
int
【在 a***u 的大作中提到】
: 下午刚面的，面试官是一个华裔abc， 人很nice。
: 题目是anagram的变种，就是给一个dictionary， 再输入一个word， 让我写个
: function去找dictionary里面是否有这个word的anagram。
: 我先是想到了LC的anagram，就说把每个dictionary 里面的sort 一下然后存个hashmap
: 。她说行，开始编程。完事后面试官让我试不同的testcase，问复杂度并且，我说O（
: nklgk）. 她问能不能更efficent一点。我说用个对每个dictionary的word建立一个int
: array，然后统计每个char的出现次数 这样应该是O(nk)。她问有没有别的方法，我就
: 说可以不用array, 用hashmap 统计（我实在想不到别的办法了）。面试官又问用矩阵
: 和hashmap的区别和各自优缺点。我胡扯一通，时间到了。听面试官的语气应该还有更
: 好的解法，希望版上大牛们能指导一下。总体上说面试官人很nice，也没为难我，经常
|
w*****1
发帖数: 6807 | 15 对，就是这个想法
【在 w********m 的大作中提到】
: permutation的改写吧。发现anagram立即退出，最坏复杂度k!
:
: hashmap
: int
|
P***P
发帖数: 1387 | |
a***u
发帖数: 383 | 17 不是问矩阵和hash的区别。我不是答题时先说用array统计word的char，然后说用个
hashmap 也可以做这样的统计。她问用这两个有什么区别，我想了想用这两个数据结构
按我当时想的那个方法复杂度应该是一样的，又不敢直接说没区别，就胡说了一通。
【在 n******n 的大作中提到】
: 矩阵和hash的区别？这完全两回事啊。
:
: hashmap
: int
|
m********g
发帖数: 1489 | 18 k! can be too huge. e.g. 'industrialization'
【在 w********m 的大作中提到】
: permutation的改写吧。发现anagram立即退出，最坏复杂度k!
:
: hashmap
: int
|
k******a
发帖数: 44 | 19
在这个问题上是没有区别，因为26个字母，访问时间也是O(1)，空间也是O(1)
【在 a***u 的大作中提到】
: 不是问矩阵和hash的区别。我不是答题时先说用array统计word的char，然后说用个
: hashmap 也可以做这样的统计。她问用这两个有什么区别，我想了想用这两个数据结构
: 按我当时想的那个方法复杂度应该是一样的，又不敢直接说没区别，就胡说了一通。
|
k******a
发帖数: 44 | 20 从word方向下手是很好，但是只能解决一个word的问题，第二个word还是需要k!
但是字典的hashmap一旦做好，对于任何输入的word，都是O(1) |
|
|
g*****g
发帖数: 34805 | 21 就是把字典里所有词自身按字符排序为key做成hashmap，然后找的时候keyword也自己
排序以下就好
了。O(klogk)的查找。要比k!快多了。 |
T*****u
发帖数: 7103 | 22 1. sort each word in the dictionary in alphabeta order, also save the order
of each letter, e.g., bag is abg, and order array is 102
2. save all the words in dictionary in a tree (ref. leetcode or some where),
instead of None/Null, using the int array to terminate the node
3. search a word of length k will take O(k) |
d*********n
发帖数: 8 | 23 How about overriding hashmap's hashcode ?这样在处理dictionary的时候就可以顺
便归类anagrams了，然后直接mp.get(input word), 复杂度是O(N) 不考虑hashcode的
计算时间的话。 |
w**z
发帖数: 8232 | 24 把dictionary 的词排序后做key
【在 d*********n 的大作中提到】
: How about overriding hashmap's hashcode ?这样在处理dictionary的时候就可以顺
: 便归类anagrams了，然后直接mp.get(input word), 复杂度是O(N) 不考虑hashcode的
: 计算时间的话。
|
w**z
发帖数: 8232 | 25 这最简单易懂了。
【在 g*****g 的大作中提到】
: 就是把字典里所有词自身按字符排序为key做成hashmap，然后找的时候keyword也自己
: 排序以下就好
: 了。O(klogk)的查找。要比k!快多了。
|
v******F
发帖数: 61 | 26 把keyword 放进 hashmap eg, "hello" h=1 , e=1, l=2, 0=1
读进字典， 比较length，length 不等去掉。 length 相等 看 hashmap 里面 keys,一
旦key 没有，就下一个， 如果key有就hashmap[key]--, 当等于0时，就把key去掉。
在不常search的时候， 应该可以用
常用的话：
就以SORTED 的字为KEY， VALUE是 anagram 的 LIST |
