Q:

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

输入:

words = [“oath”,“pea”,“eat”,“rain”] and board =

[

[‘o’,‘a’,‘a’,‘n’],

[‘e’,‘t’,‘a’,‘e’],

[‘i’,‘h’,‘k’,‘r’],

[‘i’,‘f’,‘l’,‘v’]

]

输出: [“eat”,“oath”]

说明:

你可以假设所有输入都由小写字母 a-z 组成。

提示:

你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？

如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

A:

对给定单词表建立前缀树，从矩阵每个位置开始向上下左右dfs寻找，当前遍历过的位置置为’$’，成功查找到的单词在前缀树中做相应记录，防止之后的dfs再次查找该单词。

class Solution:

    def findWords(self, board, words):

        rows=len(board)

        if not rows:

            return []

        cols=len(board[0])

        trie={}

        res=[]

        for word in words:

            t=trie

            for x in word:

                if x not in t:

                    t.setdefault(x,{})

                t=t[x]

            t['end']=1

        def dfs(i,j,cur_word,node):

            nonlocal rows,cols,res

            c=board[i][j]

            if c not in node:

                return

            node=node[c]

            if 'end' in node:

                if node['end']==1:

                    res.append(cur_word+c)

                    node['end']=0

            board[i][j]='$'

            for ii,jj in [(0,1),(0,-1),(1,0),(-1,0)]:

                xx,yy=i+ii,j+jj

                if 0<=xx<rows and 0<=yy<cols and board[xx][yy]!='$':

                    dfs(xx,yy,cur_word+c,node)

            board[i][j]=c

        for i in range(rows):

            for j in range(cols):

                dfs(i,j,'',trie)

        return res

212. 单词搜索 II的相关教程结束。