单词搜索 II

难度: Hard

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。

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

示例 1：

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

示例 2：

输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 10⁴
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

Submission

运行时间: 468 ms

内存: 0.0 MB

dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
class TrieNode:
    def __init__(self):
        self.children = {} #{letter:trienode of subtree}
        self.is_word = False
        self.word = None

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def add(self, word):		#字典树插入单词
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()   #在此节点申请节点
            node = node.children[c]     		#继续遍历
        node.is_word = True
        node.word = word        #存入单词
    
    #def find(self,word):
     #   node = self.root
      #  for c in word:
       #     node = node.children.get(c)
        #    if node is None:
         #       return None
                
        #return node.is_word
        
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board or not board[0] or not words:
            return []
        trie = Trie()
        for w in words:    #建立字典树,将所有dict中word放入字典树
            trie.add(w)
        output = []
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                c = board[i][j]
                #从字典树root开始搜索
                self.dfs(board,trie.root.children.get(c),i,j,[[i,j]],output)
        return output
                
    def dfs(self,board,node,x,y,visited,output):
        if not node:
            return
        if node.is_word and node.word not in output:
            output.append(node.word)
        
        for d in dirs:
            new_x = x+d[0]
            new_y = y+d[1]
            if new_x<0 or new_x>=len(board) or new_y<0 or new_y>=len(board[0]):
                continue
            if [new_x,new_y] in visited:
                continue
            
            visited.append([new_x,new_y])
            self.dfs(board,node.children.get(board[new_x][new_y]),new_x,new_y,visited,output)
            visited.pop()

Explain

这个题解使用了字典树（Trie）和深度优先搜索（DFS）的方法来解决单词搜索问题。首先，将所有需要搜索的单词构建成一棵字典树。然后，对于网格中的每个字符，从该字符开始进行DFS搜索。在DFS过程中，沿着字典树匹配字符，同时在网格上向四个方向扩展。如果在字典树的某个节点匹配到完整的单词，就将该单词加入到输出结果中。为了避免重复访问网格上的字符，使用一个visited数组来记录已访问过的位置。

时间复杂度: O(m*n*4^w + k*w)

空间复杂度: O(k*w)

```python
dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
class TrieNode:
    def __init__(self):
        self.children = {} #{letter:trienode of subtree}
        self.is_word = False
        self.word = None

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def add(self, word):  #字典树插入单词
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()   #在此节点申请节点
            node = node.children[c]             #继续遍历
        node.is_word = True
        node.word = word        #存入单词
        
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board or not board[0] or not words:
            return []
        trie = Trie()
        for w in words:    #建立字典树,将所有dict中word放入字典树
            trie.add(w)
        output = []
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                c = board[i][j]
                #从字典树root开始搜索
                self.dfs(board,trie.root.children.get(c),i,j,[[i,j]],output)
        return output
                
    def dfs(self,board,node,x,y,visited,output):
        if not node:
            return
        if node.is_word and node.word not in output:
            output.append(node.word)
        
        for d in dirs:
            new_x = x+d[0]
            new_y = y+d[1]
            if new_x<0 or new_x>=len(board) or new_y<0 or new_y>=len(board[0]):
                continue
            if [new_x,new_y] in visited:
                continue
            
            visited.append([new_x,new_y])
            self.dfs(board,node.children.get(board[new_x][new_y]),new_x,new_y,visited,output)
            visited.pop()
```

Explore

`is_word`标志用于指示当前节点是否表示一个完整的单词的结束。这对于区分仅是其他单词前缀的字符序列和实际存储在字典树中作为独立单词的字符序列非常重要。例如，'app'和'apple'，在'p'节点上的`is_word`标志表示'app'是一个完整的单词。而`word`属性存储的是从根到当前节点形成的完整单词，这样在找到一个完整单词时可以直接从节点获取，而不需要重新遍历从根到该节点的路径来重建单词。

使用`visited`列表可以帮助我们记录哪些位置已经被访问过，从而避免在DFS过程中重复访问相同的格子。这样做的好处是避免破坏原始`board`的内容，因为直接修改`board`的字符可能会丢失原始数据，而使用`visited`列表则可以在DFS完成后保留完整的`board`。此外，使用`visited`列表还可以灵活地添加和删除访问记录，便于控制和回溯访问路径。

在DFS中检查新的坐标是否已在`visited`列表中是防止重复访问同一位置的重要步骤。由于每个位置只应在一个搜索路径中被访问一次，这可以确保搜索不会进入循环或重复覆盖已探索的路径。这种检查帮助维护了搜索的正确性和效率，防止无限递归和路径的重复探索。

如果`words`列表中的单词非常长，这将对算法的性能产生几个影响：1. 构建字典树的时间和空间复杂度会增加，因为长单词意味着更多的节点和更深的树结构。2. DFS过程中的搜索深度会增加，这可能导致更高的递归开销和更长的搜索时间。3. 随着单词长度的增加，匹配过程中遍历字典树的路径也变得更长，这可能导致在每一步中检查更多的可能性，从而增加算法的执行时间。因此，单词非常长时，整体的时间和空间需求都会上升，降低算法的效率。