Tree solutions, 18-20 lines


  • 22
    class WordDictionary:
    
        def __init__(self):
            self.root = {}
        
        def addWord(self, word):
            node = self.root
            for char in word:
                node = node.setdefault(char, {})
            node[None] = None
    
        def search(self, word):
            def find(word, node):
                if not word:
                    return None in node
                char, word = word[0], word[1:]
                if char != '.':
                    return char in node and find(word, node[char])
                return any(find(word, kid) for kid in node.values() if kid)
            return find(word, self.root)
    

    An iterative alternative for the search method:

        def search(self, word):
            nodes = [self.root]
            for char in word:
                nodes = [kid
                         for node in nodes
                         for key, kid in node.items()
                         if char in (key, '.') and kid]
            return any(None in node for node in nodes)
    

    And one that's a bit longer but faster:

        def search(self, word):
            nodes = [self.root]
            for char in word:
                nodes = [kid for node in nodes for kid in
                         ([node[char]] if char in node else
                          filter(None, node.values()) if char == '.' else [])]
            return any(None in node for node in nodes)
    

    And a neat version where I append my end-marker to the word to simplify the final check:

    class WordDictionary:
    
        def __init__(self):
            self.root = {}
        
        def addWord(self, word):
            node = self.root
            for char in word:
                node = node.setdefault(char, {})
            node['$'] = None
    
        def search(self, word):
            nodes = [self.root]
            for char in word + '$':
                nodes = [kid for node in nodes for kid in
                         ([node[char]] if char in node else
                          filter(None, node.values()) if char == '.' else [])]
            return bool(nodes)

  • 0
    S

    Oh it's so brilliant to implement a tree structure using dicts!!


  • 0
    This post is deleted!

  • 0

    Looks really elegant, but not quite understand it.. I need to know more about Python.


  • 4
    S

    Do you know about this trick? It makes tries very nice

    from collections import defaultdict
        
    def _trie():
        return defaultdict(_trie)

  • 0

    I know it now :-)
    Nice one, thanks.


  • 0
    W
    This post is deleted!

  • 0
    O

    8-liner in Python. I used some tricks posted here.

    class WordDictionary(object):
        def __init__(self):
            self.root = {}
    
        def addWord(self, word):
            cur = self.root
            for c in word:
                cur = cur.setdefault(c, {})
            cur[None] = 'isWord'
    
        def search(self, word):
            def f(n, w):
                return any(f(n[x], w[1:]) for x in (n if w[0]=='.' else [w[0]]) if x and x in n) if w else None in n
            return f(self.root, word)
    

  • 0
    Z

    @severb

    you idea is very impressive, I implemented it here with "one" line for each function

    https://discuss.leetcode.com/topic/78602/python-each-function-only-one-line


  • 0

    @StefanPochmann
    Very similar solution:

    class WordDictionary(object):
        def __init__(self):
            self.trie = dict()
    
        def addWord(self, word):
            cur = self.trie
            for c in word + "$": cur = cur.setdefault(c, {})
    
        def search(self, word, cur=None):
            if not cur: cur = self.trie
            return "$" in cur if not word \
                else self.search(word[1:], cur[word[0]]) if word[0] in cur \
                else False if 'a' <= word[0] <= 'z' \
                else any(self.search(word[1:], cur[c]) for c in cur if c!="$")

Log in to reply
 

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