@awice I actually ran three code snippets and compared their run time. The first hash and trie took 19ms, whereas second hash took 133ms. I think it proves my thought, which is the time complexity of first hash method is O(sigma(Wi)) that equals to trie method, while such of the second hash method is O(nlogn * m).
Heronalps
@Heronalps
26
Reputation
37
Posts
296
Profile views
0
Followers
0
Following
Posts made by Heronalps

RE: Longest Word In Dictionary

RE: Longest Word In Dictionary
@derek3 @snailandmail Can you explain why the time complexity of approach #1 is O(nlogn * M)? If the sorting takes O(nlogn), the search operation is parallel to the sorting. Why should I multiply (nlogn) by M? Thank you in advance.

RE: Longest Word In Dictionary
@awice Hi, Can you explain a bit more about why time complexity of approach #1 is O(sigma(Wi^2))? In my perspective, since we already have a hash set that contains all words, the search operation is O(1). For each word, we only need O(Wi) to find if all prefixes are in the hash set. Thus, the overall time complexity is O(sigma(Wi)). Sorry if my question is dump...