LeetCode 212. 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(t.Search(cur)) ret.Add(cur); 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; } } }