# 0212. Word Search II

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

## Description

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.

## ac

```java
class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<String>();
        // edge cases
        if (board.length == 0 || board[0].length == 0 || words.length == 0) {
            return res;
        }

        // build trie
        TrieNode root = new TrieNode();
        root.build(words);

        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfs(board, r, c, root, res);
            }
        }

        return res;
    }

    private void dfs(char[][] board, int r, int c, TrieNode node, List<String> res) {
        // out of boundary?
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return;

        // visited in this word? current char not in trie? return
        int pos = board[r][c] - 'a';
        if (board[r][c] == '#' || node.next[pos] == null) return;

        // continue, mark visited
        char curr = board[r][c];
        board[r][c] = '#';

        // find word
        if (node.next[pos].word != null) {
            res.add(node.next[pos].word);
            node.next[pos].word = null;
        }

        // adjacent chars
        dfs(board, r+1, c, node.next[pos], res);
        dfs(board, r-1, c, node.next[pos], res);
        dfs(board, r, c+1, node.next[pos], res);
        dfs(board, r, c-1, node.next[pos], res);

        // resume visited mark
        board[r][c] = curr;
    }

}

class TrieNode {
    public TrieNode[] next;
    String word;

    public TrieNode() {
        next = new TrieNode[26];
    }

    public void insert(String s, int index) {
        if (index == s.length()) {
            this.word = s;
            return;
        }
        int i = s.charAt(index) - 'a';
        if (next[i] == null) next[i] = new TrieNode();
        next[i].insert(s, index+1);
    }

    public void build(String[] words){
        for (String w : words) {
            insert(w, 0);
        }
    }
}

// build a trie, node with a string
// walk board, current char in trie? continue : return;
//board[r][c] - 'a'
```
