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(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;
        }
    }
}