# LeetCode-Word Search II  Solution
Date: 2021-03-07


#### **问题：**

Given an `m x n` `board` of characters and a list of strings `words`, return _all words on the board_.

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

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/11/07/search1.jpg)**Input:**

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

```

**Output:**

```
 ["eat","oath"]

```

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/11/07/search2.jpg)

**Input:**

```
 board = [["a","b"],["c","d"]], words = ["abcb"]

```

**Output:**

```
 []

```

 

**Constraints:**

- `m == board.length`
- `n == board[i].length`
- `1 <= m, n <= 12`
- `board[i][j]` is a lowercase English letter.
- `1 <= words.length <= 3 * 10`4
- `1 <= words[i].length <= 10`
- `words[i]` consists of lowercase English letters.
- All the strings of `words` are unique.

 

#### **解答：**

深度优先遍历DFS。使用“#”标识了已经遍历的节点的信息，将单词存放到Trie，上下左右四个方向通过调用DFS递归函数在二维数组中进行查找匹配

```
class TrieNode():
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.isWord = False
class Trie():
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for w in word:
            node = node.children[w]
        node.isWord = True
        
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        res = []
        trie = Trie()
        node = trie.root
        for w in words:
            trie.insert(w)
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.dfs(board, node, i, j , "", res)
        return res
    
    def dfs(self, board, node, i, j, path, res):
        if node.isWord:
            res.append(path)
            node.isWord = False
            
        if i < 0 or i >= len(board) or j<0 or j>=len(board[0]):
            return 
         
        char = board[i][j]
        node = node.children.get(char)
        if not node:
            return 
        board[i][j] = "#"
        self.dfs(board, node, i+1, j, path+char, res)
        self.dfs(board, node, i-1, j, path+char, res)
        self.dfs(board, node, i, j-1, path+char, res)
        self.dfs(board, node, i, j+1, path+char, res)
        board[i][j] = char

```

 

#### **参考及引用**

图片来自 twitter Ines B @moraimauy

[Python-dfs-solution-(directly-use-Trie-implemented).](https://leetcode.com/explore/learn/card/trie/149/practical-application-ii/1056/discuss/59790/Python-dfs-solution-\(directly-use-Trie-implemented\).)