LeetCode 211. Add and Search Word – Data structure design
Add and Search Word – Data structure design
public class WordDictionary { class TrieNode { public TrieNode[] Children = new TrieNode[26]; public bool IsWord = false; } TrieNode Root = new TrieNode(); /** Initialize your data structure here. */ public WordDictionary() { } /** Adds a word into the data structure. */ public void AddWord(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 data structure. A word could contain the dot character '.' to represent any one letter. */ public bool Search(string word) { return Search(word, Root); } private bool Search(string word, TrieNode cur){ char c = word[0]; if(c != '.'){ int index = c - 'a'; if(cur.Children[index] == null) return false; cur = cur.Children[index]; if(word.Length == 1){ if(cur.IsWord) return true; else return false; } else { return Search(word.Substring(1), cur); } } else { for(int i = 0; i < 26; i++){ if(cur.Children[i] == null) continue; if(word.Length == 1){ if(cur.Children[i].IsWord) return true; else continue; } if(Search(word.Substring(1),cur.Children[i])) return true; } return false; } } } /** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.AddWord(word); * bool param_2 = obj.Search(word); */