设计一个包含一些单词的特殊词典,并能够通过前缀和后缀来检索单词
实现存储所有可能前后缀组合对应最大下标
class WordFilter { private: unordered_map<string, int> dict;//记录所有前后缀组合对应最大下标 public: WordFilter(vector<string>& words) { for (int i = 0; i < words.size(); i++) { int m = words[i].size(); string word = words[i]; for (int prefixLength = 1; prefixLength <= m; prefixLength++) { for (int suffixLength = 1; suffixLength <= m; suffixLength++) { string key = word.substr(0, prefixLength) + '#' + word.substr(m - suffixLength);//键编码 dict[key] = i;//更新记录最大索引 } } } } int f(string pref, string suff) {//前缀和后缀同时匹配 string target = pref + '#' + suff; return dict.count(target) ? dict[target] : -1; } };
巧妙之处在于将前缀和后缀进行拼接,同时前缀放在后面,后缀放在前面
减少了字典树的搜索空间,使得前缀能进行复用,同时{用于拼接,直接建立了27叉树
对于所有字典树的前缀部分,都要更新记录最大索引
class Trie { private: int idx; bool end; Trie* next[27]; public: Trie() { for(int i = 0;i < 27;i ++) this->next[i] = nullptr; end = false; }; void add(string& x,int& p) { // 字典树中加入单词 x Trie* root = this; bool o = false;//用于判断什么时候到了前缀部分 for(auto& c : x) { if(!root->next[c - 'a']) root->next[c - 'a'] = new Trie();//新增节点 root = root->next[c - 'a']; if(o) root->end = true , root->idx = p;//更新记录所有前缀最大下标 if(!o && c == '{') o = true;// 第一次遇到{,说明后面的都是前缀 } } int query(string& x) { // 查询单词 x 的个数 Trie* root = this; for(auto& c : x) { if(!root->next[c - 'a']) return -1;// 如果遇到空节点 直接返回 -1 root = root->next[c - 'a']; } return root->idx;//返回下标 } }; class WordFilter { public: Trie* root; WordFilter(vector<string>& words) { root = new Trie(); for(int i = 0;i < words.size();i ++) { for(int j = 1;j <= words[i].size();j ++) { // 后缀的长度 string ts = words[i].substr(words[i].size() - j);//后缀 ts += '{'; ts += words[i];//前缀 root->add(ts,i);//所有的后缀套整个单词组合 } } } int f(string prefix, string suffix) { suffix += '{'; suffix += prefix; return root->query(suffix); } };