Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Trie(object):
- def __init__(self):
- self.children = {}
- def insert(self, word):
- if word[0] not in self.children:
- self.children[word[0]] = Trie()
- l = len(word)
- if l == 1:
- return
- self.children[word[0]].__insert(word, 1, l)
- def __insert(self, word, i, l):
- if word[i] not in self.children:
- self.children[word[i]] = Trie()
- if l - i == 1:
- return
- self.children[word[i]].__insert(word, i+1, l)
- def search(self, word):
- if word[0] not in self.children:
- return False
- l = len(word)
- if l == 1:
- return True
- return self.children[word[0]].__search(word, 1, l)
- def __search(self, word, i, l):
- if word[i] not in self.children:
- return False
- if l - i == 1:
- return True
- return self.children[word[i]].__search(word, i+1, l)
- from itertools import product
- from collections import namedtuple
- from copy import copy
- if type(board) is not list or len(board) == 0:
- return []
- if type(board[0]) is not list or len(board[0]) == 0:
- return []
- if type(words) is not list or len(words) == 0:
- return []
- m = len(board)
- n = len(board[0])
- trie = Trie()
- words = [ list(w) for w in words ]
- for word in words:
- trie.insert(word)
- Point = namedtuple('Point', ['x', 'y'])
- def crawl(_letters, c_point, _points, output):
- letters = copy(_letters)
- x = c_point.x
- y = c_point.y
- letters.append(board[x][y])
- points = _points.copy()
- points.add(c_point)
- if trie.search(letters):
- if letters in words:
- w = ''.join(letters)
- if w not in output:
- output.append(w)
- # Make Points
- adjacent_points = []
- for p in [ Point(x-1,y), Point(x+1,y), Point(x,y-1), Point(x,y+1) ]:
- if (p not in points and
- m > p.x >= 0 and
- n > p.y >= 0):
- adjacent_points.append(p)
- for p in adjacent_points:
- crawl(letters, p, points, output)
- return False
- output = []
- pointz = set()
- for i,j in product(range(m), range(n)):
- crawl([], Point(i,j), pointz, output)
- return output
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement