Python, Straightforward with Explanation (Prefix hash, Trie solutions)


  • 6

    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()))
    

  • 0
    S

    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.


  • 0

    @parvez.h.shaikh You are right, I fixed it.


  • 0
    A

    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?


  • 0

    @arpit159 I tried and it AC'ed, I used Python2 which may make a difference.


  • 0
    R

    @sha256pki I keep getting a memory limit exceeded with my own Trie... I am using an array of 26 chars for every child. Any ideas on how to fix it?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.