Design a data structure that supports the following two operations:
void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord(“bad”) addWord(“dad”) addWord(“mad”) search(“pad”) -> false search(“bad”) -> true search(“.ad”) -> true search(“b..”) -> true Note: You may assume that all words are consist of lowercase letters a-z.
Trie这种数据结构可以很方便的实现字符串的查找，它的时间复杂度只有O(L)，根据最下面的提示单词中只有a-z的小写字母这个提示也可以想到使用Trie。 前面Trie的实现使用的递归实现的，这次尝试使用非递归实现。 基本的数据结构TrieNode也做了一些改变，因为不需要进行统计计数，只需要判断是否存在以某个节点结尾的字符串，所以使用一个标示量来判断是否存在以该字符结尾的字符串即可。 搜索字符串使用的是递归，要是没有’.’这个字符可能用非递归也比较好实现，但是加上’.’这个字符后用非递归想了会儿没想出了但是感觉用递归会很容易求解。 最后需要注意的是node节点的含义是字符的父节点，因为Trie树的根节点是一个空字符。 runtime:100ms
class WordDictionary {public:class TrieNode{public:TrieNode * edges[26];//子节点bool end;//标示是否有以这个节点结尾的字符串TrieNode(){for(int i=0;i<26;i++){edges[i]=NULL;}end=false;}};class Trie{public:Trie(){root=new TrieNode();}//添加单词使用循环实现，也可以使用递归，前面创建Trie树即使用的是递归void addWord(string word){if(word.empty())return ;TrieNode * node=root;int pos=0;while(pos<word.size()){int char_code=word[pos]-‘a’;if(node->edges[char_code]!=NULL){node=node->edges[char_code];pos++;}else{node->edges[char_code]=new TrieNode();node=node->edges[char_code];pos++;}}node->end=true;}//搜索使用递归实现，，要是没有’.’使用循环也很容易实现，但是加上限制条件后使用递归更容易一些bool search(string &word,int pos,TrieNode * node){if(word.empty()&&node->end)return true;int char_code=word[pos]-‘a’;if(pos==word.size()&&node->end)return true;if(char_code==’.’-‘a’){for(int i=0;i<26;i++)if(node->edges[i]!=NULL&&search(word,pos+1,node->edges[i]))return true;}else{if(node->edges[char_code]!=NULL)return search(word,pos+1,node->edges[char_code]);}}TrieNode * root;};// Adds a word into the data structure.void addWord(string word) {trie.addWord(word);}search(string word) {return trie.search(word,0,trie.root);}private:Trie trie;};
将会错过更好的风景，保持一份平和，保持一份清醒。
