211AddandSearchWordDatastructuredesign添加与搜索单词数据结构设计

class TrieNode {public TrieNode[] children;public boolean isWord &＃61; false;public TrieNode(){children&＃61;new TrieNode[26];}
}class WordDictionary {private TrieNode root;/** Initialize your data structure here. */public WordDictionary() {root&＃61;new TrieNode();}/** Adds a word into the data structure. */public void addWord(String word) {TrieNode node &＃61; root;for (char ch: word.toCharArray()) {if (node.children[ch-&＃39;a&＃39;] &＃61;&＃61; null) {node.children[ch-&＃39;a&＃39;] &＃61; new TrieNode();}node &＃61; node.children[ch-&＃39;a&＃39;];}node.isWord &＃61; true;}/** Returns if the word is in the data structure. A word could contain the dot character &＃39;.&＃39; to represent any one letter. */public boolean search(String word) {return helper(word, 0, root);}private boolean helper(String word, int start, TrieNode node) {if (start &＃61;&＃61; word.length()){return node.isWord;} char ch &＃61; word.charAt(start);if (ch &＃61;&＃61; &＃39;.&＃39;) {for (int i &＃61; 0; i <26; i&＃43;&＃43;) {if (node.children[i] !&＃61; null && helper(word, start&＃43;1, node.children[i])) {return true;}}} else {return node.children[ch-&＃39;a&＃39;] !&＃61; null && helper(word, start&＃43;1, node.children[ch-&＃39;a&＃39;]);}return false;}
}/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary obj &＃61; new WordDictionary();* obj.addWord(word);* boolean param_2 &＃61; obj.search(word);*/


class TrieNode {
public:TrieNode *next[26];char c;bool isWord;TrieNode() : isWord(false) {for (auto & c: next){c&＃61;nullptr;}}TrieNode(char _c):c(_c),isWord(false){for(auto &c:next){c&＃61;nullptr;}}
};
class WordDictionary {
public: WordDictionary() {root &＃61; new TrieNode();}// Adds a word into the data structure.void addWord(string word) {TrieNode *p &＃61; root;for (auto &c : word) {int i &＃61; c - &＃39;a&＃39;;if (!p->next[i]){p->next[i] &＃61; new TrieNode(c);}p &＃61; p->next[i];}p->isWord &＃61; true;}// Returns if the word is in the data structure. A word could// contain the dot character &＃39;.&＃39; to represent any one letter.bool search(string word) {return searchWord(word, root, 0);}bool searchWord(string &word, TrieNode *p, int i) {if (i &＃61;&＃61; word.size()){return p->isWord;}if (word[i] &＃61;&＃61; &＃39;.&＃39;){for (auto &c : p->next) {if (c && searchWord(word, c, i &＃43; 1)){return true;}}return false;}else {return p->next[word[i] - &＃39;a&＃39;] && searchWord(word, p->next[word[i] - &＃39;a&＃39;], i &＃43; 1);}}private:TrieNode *root;
};// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");