Python solution with detailed explanation

  • 0


    Word Search II

    Trie and Backtracking

    • Brute force solution would be to apply Word Search 1 for every word in the dictionary. This results in TLE.
    • Add all the words in the dictionary inside the trie.
    • Now seed the recursion such that every valid start point on the board starts a new search. Pass the co-ordinates of the start point (x,y). Also pass trie node pointer.
    • Now the terminating condition is that any immediate negihbor of (x,y) is not a valid next state.We can easily test if neighbor x1,y1 is valid using the trie_node.
    • Notice that in the trie we store the final word and not just true/false. This lets us just pass the trie pointer around.
    class TrieNode(object):
        def __init__(self):
            self.value, self.links = None, [None]*26
    class Trie(object):
        def __init__(self):
            self.root = TrieNode()
        def insert(self, word):
            if word:
                curr = self.root
                for ch in word:
                    offset = ord(ch)-ord('a')
                    if curr.links[offset] == None:
                        curr.links[offset] = TrieNode()
                    curr = curr.links[offset]
                curr.value = word
    class Solution(object):
        def helper(self, x, y, board, trie_node, result):
            if trie_node.value:
                result.add(trie_node.value) # Look for other soln even if a soln is found. soln could a prefix of another soln.
            for x1,y1 in ((x+1,y), (x-1,y), (x, y+1), (x, y-1)):
                if 0<=x1<len(board) and 0<=y1<len(board[0]) and board[x1][y1] != -1 and trie_node.links[ord(board[x1][y1])-ord('a')]:
                    ch, board[x1][y1] = board[x1][y1], -1
                    self.helper(x1, y1, board, trie_node.links[ord(ch)-ord('a')], result)
                    board[x1][y1] = ch
        def findWords(self, board, words):
            :type board: List[List[str]]
            :type words: List[str]
            :rtype: List[str]
            trie = Trie()
            for word in words:
            result = set([])
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if trie.root.links[ord(board[i][j])-ord('a')]: 
                        ch, board[i][j] = board[i][j], -1
                        self.helper(i, j, board, trie.root.links[ord(ch)-ord('a')], result)
                        board[i][j] = ch
            return [x for x in result]        

Log in to reply

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