Leetcode 211 题目解答:1. 搜索题,而且有 regular expression, 正则表达式的匹配搜索。用 "." 代表一个字母的情况如何在代码或数学上模拟呢?
2. 难道是遇到 "." 就遍历所有 child 指针不为 NULL 的下家吗?试一试先!
- //方法1:用trie, 用dfs尝试26种情况,如果遇到"."class WordDictionary {private: struct node{ node* child[26]; bool isWord; node(){ for(int i=0;i<26;i++) child[i]=NULL; isWord=false; } }; node* root;public: /** Initialize your data structure here. */ WordDictionary() { root=new node();//新建一个node,让指针指向,不能搞没有实体的指针呀! } /** Adds a word into the data structure. */ void addWord(string word) { // node* cur=root; for(char c:word){ int idx=c-'a'; if(!cur->child[idx]) cur->child[idx]=new node(); cur=cur->child[idx]; } cur->isWord=true; } /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */ bool helper(string word,node* cur,int i){ if(!cur) return false; if(i==word.size()) return cur->isWord; if(word[i]=='.'){ for(int j=0;j<26;j++) if(cur->child[j]&&helper(word,cur->child[j],i+1)) return true; return false; }else{ return helper(word,cur->child[word[i]-'a'],i+1); } } bool search(string word) { // node* cur=root; return helper(word,cur,0); }};/** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * bool param_2 = obj.search(word); */
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: