3 Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example, 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"].

https://leetcode.com/problems/word-search-ii/

思路：这其实是一道非常好的集合了2D arrar DFS和Trie的题目。看到这道题，最暴力的方法就是，直接在2D array里面一个一个单词地找。可是这样就复杂度感人了。因为首先你要loop 2D array找首字母可能的起始位置，然后从每个可能的起始位置dfs。

我们先把所有的单词建trie。然后对2D array的每一个位置根据trie来一层一层dfs。这样我们过一遍matrix就行了。在对每个位置根据trie进行dfs的时候，我们要注意不要再访问访问过的节点，然后就可以看出这里有点backtracking的意思了。我们继续dfs到其他位置的时候把这个点表成其他 ‘#’，其实存一个visited的矩阵更安全，因为matrix里的字符有可能就是‘#’。

最后结果会出现4次是因为，走到一个单词的结尾的时候，会继续从4个方向dfs下去。所以这时候我们在存好第一个的时候，要删除isword的flag，避免重复存储。

class Node(object):
    def __init__(self):
        self.dic = {}
        self.isWord = False

class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        root = Node()

        for w in words:
            cur = root
            for c in w:
                if c not in cur.dic:
                    cur.dic[c] = Node()
                cur = cur.dic[c]
            cur.isWord = True

        res = []
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.bt(i, j, board, '', root, res)
        return res

    def bt(self, i, j, board, path, root, res):
        if root.isWord:
            res.append(path)
            root.isWord = False

        if 0<=i<len(board) and 0<=j<len(board[0]):
            c  = board[i][j]
            if c in root.dic:
                board[i][j]='#'
                self.bt(i-1, j, board, path+c, root.dic[c], res)
                self.bt(i+1, j, board, path+c, root.dic[c], res)
                self.bt(i, j+1, board, path+c, root.dic[c], res)
                self.bt(i, j-1, board, path+c, root.dic[c], res)
                board[i][j]=c

这里提供另外一种写法

class Node(object):
    def __init__(self):
        self.dic = {}
        self.isWord = False

class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        root = Node()
        for w in words:
          tmp = root
          for c in w:
            if c not in tmp.dic:
              tmp.dic[c] = Node()
            tmp = tmp.dic[c]
          tmp.isWord = True

        res = []
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.dfs(board, i, j, '', root, res)
        return res

    def dfs(self, board, i, j, path, node, res):
        if node.isWord:
            res.append(path)
            node.isWord = False

        if 0<=i<len(board) and 0<=j<len(board[0]) and board[i][j] in node.dic:
            tmp = board[i][j]
            board[i][j] = '#'
            for dp in [(1,0), (-1,0), (0,1), (0,-1)]:
                m, n = i+dp[0], j+dp[1]
                self.dfs(board, m, n, path+tmp, node.dic[tmp], res)
            board[i][j] = tmp