SHARE
TWEET

Untitled

a guest Jun 17th, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution:
  2.     def __init__(self, board, words):
  3.         self.board = board
  4.         self.words = words
  5.  
  6.     def find_words(self, board, words):
  7.  
  8.         root = {}
  9.         for word in words:
  10.             node = root
  11.             for c in word:
  12.                 node = node.setdefault(c, {})
  13.             node[None] = True
  14.         board = {i + 1j * j: c
  15.                  for i, row in enumerate(board)
  16.                  for j, c in enumerate(row)}
  17.  
  18.         found = []
  19.         def search(node, z, word):
  20.             if node.pop(None, None):
  21.                 found.append(word)
  22.             c = board.get(z)
  23.             if c in node:
  24.                 board[z] = None
  25.                 for k in range(4):
  26.                     search(node[c], z + 1j ** k, word + c)
  27.                 board[z] = c
  28.         for z in board:
  29.             search(root, z, '')
  30.  
  31.         return found
  32.      
  33. output = Solution([
  34.   ['o','a','a','n'],
  35.   ['e','t','a','e'],
  36.   ['i','h','k','r'],
  37.   ['i','f','l','v']
  38. ], ["oath","pea","eat","rain"])
  39.  
  40. print(output.find_words([
  41.   ['o','a','a','n'],
  42.   ['e','t','a','e'],
  43.   ['i','h','k','r'],
  44.   ['i','f','l','v']
  45. ], ["oath","pea","eat","rain"]))
  46.  
  47. >>> ['oath', 'eat']
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top