class WordDictionary(object): def __init__(self): self.word_dict = collections.defaultdict(list) def addWord(self, word): if word: self.word_dict[len(word)].append(word) def search(self, word): if not word: return False if '.' not in word: return word in self.word_dict[len(word)] for v in self.word_dict[len(word)]: # match xx.xx.x with yyyyyyy for i, ch in enumerate(word): if ch != v[i] and ch != '.': break else: return True return False
The search function could be done in a more pythonic way, but I see that performance has suffered so I just wrote the raw logic by myself.
Nice to see that this is actually faster than a trie. Wonder if this is due to the design of test cases.
I also have this question.The "word in word_dict[len(word)]]" seems doing a search in a list? which is O(n) where n is the size of the list. am i correct? Then it will be slow if wordDictionary is huge
It's indeed faster than trie. Can you tell me how the last "else" work ? It's not in the same level with if, but what surprise me is that it does work !!
Here is a good read on "for-if-else" control flow: https://docs.python.org/2/tutorial/controlflow.html#break-and-continue-statements-and-else-clauses-on-loops.
The search function can be realized in one line (though with some loss of readability):
return any(all(x == '.' or x == word2[i] for i,x in enumerate(word)) for word2 in self.word_dict[len(word)]) if '.' in word else word in self.word_dict[len(word)]
I think this solution won't work very well in the case where there are lots of added strings with the same length.
This code runtime beats 90.22% of python submissions. I just check today.
I think there are only 13 test case for this problem which means it probably can not handle the large test case.
set nested in defaultdict is better for access, comparison, and duplicates removal (in contrast if you use list, an identical word may appear in the list multiple times if you add it multiples.).
self.word_dict = collections.defaultdict(set)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.