# Word Search II Backtracking with Trie

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.

```
public List<String> findWords(char[][] board, String[] words) {
Trie trie = buildTrie(words);
Set<String> res = new HashSet<>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs(board, trie, res, i, j);
}
}
return new ArrayList<>(res);
}
public void dfs(char[][] board, Trie node, Set<String> res, int i, int j) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
board[i][j] == '#' || node.next[board[i][j] - 'a'] == null) {
return;
}
if (node.next[board[i][j] - 'a'].word != null) {
res.add(node.next[board[i][j] - 'a'].word);
}
// Go to next char
node = node.next[board[i][j] - 'a'];
char c = board[i][j];
board[i][j] = '#';
dfs(board, node, res, i - 1, j);
dfs(board, node, res, i + 1, j);
dfs(board, node, res, i, j - 1);
dfs(board, node, res, i, j + 1);
board[i][j] = c;
}
public Trie buildTrie(String[] words) {
Trie root = new Trie();
for (String w : words) {
Trie p = root;
for (char c : w.toCharArray()) {
if (p.next[c - 'a'] == null) {
p.next[c - 'a'] = new Trie();
}
p = p.next[c - 'a']; // will point to curr char
}
p.word = w;
}
return root;
}
private class Trie {
Trie[] next = new Trie[26];
String word = null;
}
```

## Related Problems

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one **sorted** list. The list should be made by splicing together the nodes of the first two lists.

Return *the head of the merged linked list*.

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

Given a binary tree, determine if it is **height-balanced**.