# LeetCode 212. Word Search II

Word Search II

Backtracking + Trie.

```
public class Solution {
public IList<string> FindWords(char[,] board, string[] words) {
Trie t = new Trie();
foreach(string s in words) t.Insert(s);
HashSet<string> ret = new HashSet<string>();
for(int i = 0; i < board.GetLength(0); i++){
for(int j = 0; j < board.GetLength(1); j++){
bool[,] visited = new bool[board.GetLength(0), board.GetLength(1)];
Search(i, j, (new StringBuilder()).Append(board[i,j]), t, visited, ret, board);
}
}
return ret.ToList();
}

private void Search(int i, int j, StringBuilder sb, Trie t, bool[,] visited, HashSet<string> ret, char[,] board){
string cur = sb.ToString();
if(!t.StartsWith(cur)) return;
visited[i,j] = true;
if(i > 0 && !visited[i-1, j]) {
sb.Append(board[i-1, j]);
Search(i-1, j, sb, t, visited, ret, board);
sb.Length -= 1;
}
if(j > 0 && !visited[i, j-1]) {
sb.Append(board[i, j-1]);
Search(i, j-1, sb, t, visited, ret, board);
sb.Length -= 1;
}
if(i < board.GetLength(0)-1 && !visited[i+1, j]) {
sb.Append(board[i+1, j]);
Search(i+1, j, sb, t, visited, ret, board);
sb.Length -= 1;
}
if(j < board.GetLength(1)-1 && !visited[i, j+1]) {
sb.Append(board[i, j+1]);
Search(i, j+1, sb, t, visited, ret, board);
sb.Length -= 1;
}
visited[i,j] = false;
}

public class Trie {
class TrieNode {
public TrieNode[] Children = new TrieNode[26];
public bool IsWord = false;
}

TrieNode Root = new TrieNode();

/** Initialize your data structure here. */
public Trie() {
}

/** Inserts a word into the trie. */
public void Insert(string word) {
TrieNode cur = Root;
for(int i = 0; i < word.Length; i++){
int index = word[i] - 'a';
if(cur.Children[index] == null) cur.Children[index] = new TrieNode();
cur = cur.Children[index];
}
cur.IsWord = true;
}

/** Returns if the word is in the trie. */
public bool Search(string word) {
TrieNode cur = Root;
for(int i = 0; i < word.Length; i++){
int index = word[i] - 'a';
if(cur.Children[index] == null) return false;
cur = cur.Children[index];
}
if(cur.IsWord) return true;
return false;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public bool StartsWith(string prefix) {
TrieNode cur = Root;
for(int i = 0; i < prefix.Length; i++){
int index = prefix[i] - 'a';
if(cur.Children[index] == null) return false;
cur = cur.Children[index];
}
return true;
}
}
}

```