leetcode 困难题 745.Prefix and Suffix Search 前缀和后缀搜索

Problem: 745. Prefix and Suffix Search 前缀和后缀搜索

解题过程

ASCII内，"{"刚好在"z"后面，所以算是特殊字符，按照提示拼起来，然后放入到字典树当中去，并且在{后面的前缀需要求出最大的索引

查询的话直接在字典树上面找就可以，若是空则-1，最后返回最大的索引

Code

class trie { public: bool isend = false; int index = -1; trie* arr[27] = {nullptr}; }; class WordFilter { public: trie* root, *ptr; WordFilter(vector<string>& words) { root = new trie; string tp; for( int i = 0; i < words.size(); i++ ) { ptr = root; tp = "-" + words[i] + "{" + words[i]; while(true) { ptr = root; tp = tp.substr(1, tp.size() - 1); bool pre = false; for(int j = 0; j < tp.size(); j++) { if(ptr->arr[tp[j]-'a'] == nullptr) { ptr->arr[tp[j]-'a'] = new trie; } ptr = ptr->arr[tp[j]-'a']; if(pre) { ptr->index = max(ptr->index, i); } if(tp[j]=='{') pre = true; } if(tp[0]=='{') break; } } } int f(string pref, string suff) { string combine = suff + "{" + pref; ptr = root; for(int i = 0; i < combine.size(); i++) { if(ptr->arr[combine[i]-'a']==nullptr) { return -1; } ptr = ptr->arr[combine[i]-'a']; } return ptr->index; } }; /** * Your WordFilter object will be instantiated and called as such: * WordFilter* obj = new WordFilter(words); * int param_1 = obj->f(pref,suff); */