> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/4.depth-first-search/212.-word-search-ii-m.md).

# 212. Word Search II (M)

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 * 104`
* `1 <= words[i].length <= 10`
* `words[i]` consists of lowercase English letters.
* All the strings of `words` are unique.

### Solution:

<https://www.jiuzhang.com/problem/word-search-ii/>\
**Version Trie:**

使用了 Trie 的版本 考点：

* 字典树
* dfs
* tip:Tire树，一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

题解：

* 首先建立字典树，字典树从root开始，每个节点利用hashmap动态开点，利用字母的公共前缀建树。
* 遍历字母矩阵，将字母矩阵的每个字母，从root开始dfs搜索，搜索到底部时，将字符串存入答案返回即可。

```
class TrieNode {			//定义字典树的节点
    String word;
    HashMap<Character, TrieNode> children;   //使用HashMap动态开节点
    public TrieNode() {
        word = null;
        children = new HashMap<Character, TrieNode>();
    }
};


class TrieTree{
    TrieNode root;
    
    public TrieTree(TrieNode TrieNode) {
        root = TrieNode;
    }
    
    public void insert(String word) {		//字典树插入单词
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {		
            if (!node.children.containsKey(word.charAt(i))) {
                node.children.put(word.charAt(i), new TrieNode());
            }
            node = node.children.get(word.charAt(i));
        }
        node.word = word;
    }
};

public class Solution {
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    public int[] dx = {1, 0, -1, 0};   //搜索方向
    public int[] dy = {0, 1, 0, -1};
    
    public void search(char[][] board,			//在字典树上dfs查找
                       int x,
                       int y,
                       TrieNode root,
                       List<String> results) {
        if (!root.children.containsKey(board[x][y])) {
            return;
        }
        
        TrieNode child = root.children.get(board[x][y]);
        
        if (child.word != null) {      //如果访问到字典树叶子，将字符串压入result即可
            if (!results.contains(child.word)) {
                results.add(child.word);
            }
        }
        
        char tmp = board[x][y];
        board[x][y] = 0;  // mark board[x][y] as used
        
        for (int i = 0; i < 4; i++) {      //向四个方向dfs搜索
            if (!isValid(board, x + dx[i], y + dy[i])) {
                continue;
            }
            search(board, x + dx[i], y + dy[i], child, results);
        }
        
        board[x][y] = tmp;  // revert the mark
    }
    
    private boolean isValid(char[][] board, int x, int y) {     //检测搜索位置合法
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
            return false;
        }
        
        return board[x][y] != 0;
    }
    
    public List<String> wordSearchII(char[][] board, List<String> words) {
        List<String> results = new ArrayList<String>();
        
        TrieTree tree = new TrieTree(new TrieNode());
        for (String word : words){
            tree.insert(word);
        }
        
        for (int i = 0; i < board.length; i++) {				//遍历字母矩阵，将每个字母作为单词首字母开始搜索
            for (int j = 0; j < board[i].length; j++) {
                search(board, i, j, tree.root, results);
            }
        }
        
        return results;
    }
}
```

**Version 2: HashMap**

使用 HashMap 的版本。 将所有的单词的 Prefix 都加入 HashMap 中。HashMap 的 value 用户判断这是一个 prefix 还是一个 word。 如果是 prefix 就是 false，如果是 word 就是 true.

```
class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        
        int m = board.length;
        int n = board[0].length;
        Map<String, Boolean> prefixMap = getPrefixMap(words);
        boolean[][] visited = new boolean[m][n];
        Set<String> result = new HashSet<String>();
        
        for(int i = 0; i< m;i++)
        {
            for(int j = 0; j< n; j++)
            {
                visited[i][j] = true;
                dfs(board, i, j,  String.valueOf(board[i][j]), prefixMap, visited, result);
                visited[i][j] = false;
            }
        }
         return new ArrayList<>(result);                                    
                                         
    }
    
    public Map<String, Boolean> getPrefixMap(String[] words)
    {
        Map<String, Boolean> map = new HashMap<>();
        for(String word: words)
        {
            for(int i = 0; i< word.length()-1; i++)
            {
                String current = word.substring(0,i+1);
                if(!map.containsKey(current))
                {
                    map.put(current, false);
                }
            }
            map.put(word, true);
        }
        return map;
    }
    
    public void dfs(char[][] board, 
                    int x, 
                    int y, 
                    String word, 
                    Map<String, Boolean> prefixMap,
                    boolean[][] visited, 
                    Set<String> result)
    {
        if(!prefixMap.containsKey(word))
        {
            return;
        }
        if(prefixMap.get(word))
        {
            result.add(word);
        }
        
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        for(int i=0; i< 4; i++)
        {
            int nextX = x+dx[i];
            int nextY = y+dy[i];
            if(isBound(board, nextX, nextY) && !visited[nextX][nextY])
            {
                visited[nextX][nextY] = true;
                dfs(board, nextX, nextY, word+board[nextX][nextY], prefixMap, visited, result);
                visited[nextX][nextY] = false;
            }
        }
    }
    
    public boolean isBound(char[][] board, 
                    int x, 
                    int y)
    {
        return x>=0 && x<board.length && y>=0 && y< board[0].length;
    }
}
```

Follow up:&#x20;

Find a path:

[https://app.gitbook.com/s/mJ9CI3NPRUiNTweCYXsQ/oa/karat/find-word-path-in-grid](https://junnie.gitbook.io/wayfair/oa/karat/find-word-path-in-grid)