We can check the prefixes directly. For each word in the sentence, we'll look at successive prefixes and see if we saw them before.
def replaceWords(self, roots, sentence): rootset = set(roots) def replace(word): for i in xrange(1, len(word)): if word[:i] in rootset: return word[:i] return word return " ".join(map(replace, sentence.split()))
We could also use a trie. We'll insert each root in the trie. Then, for each word in the sentence, we'll replace it with the first root we encounter upon traversal of the trie.
def replaceWords(self, roots, sentence): _trie = lambda: collections.defaultdict(_trie) trie = _trie() END = True for root in roots: cur = trie for letter in root: cur = cur[letter] cur[END] = root def replace(word): cur = trie for letter in word: if letter not in cur: break cur = cur[letter] if END in cur: return cur[END] return word return " ".join(map(replace, sentence.split()))
Good solutions, I implemented my own trie class on similar lines and did not get memory limit exceeded.
Thank you for sharing "defaultdict" way of implementing trie, an excellent pythonic solution for trie.
Thanks for a neat solution. I am getting time limited exceeded error when I am feeding your solution to grader on the site. Can you confirm if it is accepted when you try on your end by the site?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.