Word Search II

题目描述

Given words = ["oath","pea","eat","rain"] and board =

[ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] Return ["eat","oath"].

解题方法

brute force

将字典里的每一个数用word seach I的DFS方法做一遍

trie

与1不同的就是这里要找board里能组成的word是否在words的字典里，对于字典的搜索 我们可能快速的想到trie.用trie来对每一个可能的word搜索，并且用is_word判断是否是 word，就可以提高效率。

主要思想还是DFS,这里加入了Trie,方便早点退出和判断word.

Solution

class TrieNode(object):
    def __init__(self):
        self.is_word = False
        self.children = {}

class Trie(object):
    def __init__(self):
        # root node
        self.root = TrieNode()

    def insert(self, word):
        current = self.root
        for letter in word:
            if letter not in current.children:
                current.children[letter] = TrieNode()
            current = current.children[letter]
        current.is_word = True

    def search(self, word):
        current = self.root
        for letter in word:
            if letter not in current.children:
                return False
            current = current.children[letter]
        return current.is_word

    def startsWith(self, prefix):
        current = self.root
        for letter in prefix:
            if letter not in current.children:
                return False
            current = current.children[letter]
        return True

class Solution(object):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        trie = Trie()
        for word in words:
            trie.insert(word)

        results = []
        row_num = len(board)
        col_num = len(board[0])
        visited = [[False for i in range(col_num)] for j in range(row_num)]

        def dfs(word, node, row, col): # inner function
            cur_node = node.children.get(board[row][col])
            if not cur_node:
                return
            visited[row][col] = True
            for i in range(4):
                x = row + self.dx[i]
                y = col + self.dy[i]
                if x >= 0 and x < len(board) and y >= 0 and y < len(board[0]) and not visited[x][y]:
                    dfs(word + board[x][y], cur_node, x, y)
            if cur_node.is_word:
                results.append(word)
                cur_node.is_word = False # so don't add it again
            visited[row][col] = False


        for i in range(row_num):
            for j in range(col_num):
                dfs(board[i][j], trie.root, i, j)

        return results

Reference