27 lines, uses complex numbers


  • 18

    I first build the tree of words with root root and also represent the board a different way, namely as one-dimensional dictionary where the keys are complex numbers representing the row/column indexes. That makes further work with it easier. Looping over all board positions is just for z in board, the four neighbors of a board position z are just z + 1j**k (for k in 0 to 3), and I don't need to check borders because board.get just returns "None" if I request an invalid position.

    After this preparation, I just take the tree and recursively dive with it into each board position. Similar to how you'd search a single word, but with the tree instead.

    class Solution:
        def findWords(self, board, words):
    
            root = {}
            for word in words:
                node = root
                for c in word:
                    node = node.setdefault(c, {})
                node[None] = True
            board = {i + 1j*j: c
                     for i, row in enumerate(board)
                     for j, c in enumerate(row)}
    
            found = []
            def search(node, z, word):
                if node.pop(None, None):
                    found.append(word)
                c = board.get(z)
                if c in node:
                    board[z] = None
                    for k in range(4):
                        search(node[c], z + 1j**k, word + c)
                    board[z] = c
            for z in board:
                search(root, z, '')
    
            return found

  • 0
    Z

    wow, such an elegant solution!


  • 2
    X

    Learned a lot. Please post more python solution :)


  • 1
    G

    @StefanPochmann

    What about just store the word at the corresponding ending node and avoid to do string adding like this:

    class Solution:
        def findWords(self, board, words):
            root = {}
            for word in words:
                node = root
                for c in word:
                    node = node.setdefault(c, {})
                node[''] = word
            board = {i + 1j*j: c
                     for i, row in enumerate(board)
                     for j, c in enumerate(row)}
            found = []
            def search(node, z):
                if '' in node:
                    found.append(node.pop(''))
                c = board.get(z)
                if c in node:
                    board[z] = '#'
                    for k in range(4):
                        search(node[c], z + 1j**k)
                    board[z] = c
            for z in board:
                search(root, z)
            return found
    

  • 0

    @SamuraiLucifer Good idea. It's not needed, but it does help a bit and it doesn't cost extra space because the words already exist and remain in the given words list anyway.


Log in to reply
 

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