Word Search II

Question

Given a matrix of lower alphabets and a dictionary. Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position.

Example

Given matrix:

doaf
agai
dcan

and dictionary:

{"dog", "dad", "dgdg", "can", "again"}

return `{"dog", "dad", "can", "again"}``

Challenge

Using trie to implement your algorithm.

Thoughts

这一题要用trie来做当然要先复习一下如何implement一个trie树 九章

算法参考-书影博客

Solution

class Solution:
    # @param board, a list of lists of 1 length string
    # @param words: A list of string
    # @return: A list of string
    def wordSearchII(self, board, words):
        # write your code here
        height = len(board)
        width = len(board[0])
        trie = Trie()
        for word in words:
            trie.insert(word)

        visited = [[False for i in range(width)] for j in range(height)]
        dx = [0,0,-1,1]
        dy = [1,-1,0,0]

        result = []

        def dfs(word, node, x, y):
            node = node.childs.get(board[x][y])
            if not node:
                return
            visited[x][y] = True
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx >= 0 and nx < height and ny >=0 and ny < width and not visited[nx][ny]:
                    dfs(word + board[nx][ny], node, nx, ny)
            if node.isWord:
                result.append(word)
                node.isWord = False
            visited[x][y] = False

        for x in range(height):
            for y in range(width):
                dfs(board[x][y], trie.root, x, y)

        return result



class TrieNode:
    # Initialize your data structure here.
    def __init__(self):
        self.childs = dict()
        self.isWord = False

class Trie:

    def __init__(self):
        self.root = TrieNode()

    # @param {string} word
    # @return {void}
    # Inserts a word into the trie.
    def insert(self, word):
        node = self.root
        for letter in word:
            child = node.childs.get(letter)
            if child is None:
                child = TrieNode()
                node.childs[letter] = child
            node = child
        node.isWord = True