LeetCode/前缀和后缀搜索（字典树）

本文主要是介绍LeetCode/前缀和后缀搜索（字典树），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词

1. 暴力哈希

实现存储所有可能前后缀组合对应最大下标

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;
    }
};

2. 字典树

巧妙之处在于将前缀和后缀进行拼接，同时前缀放在后面，后缀放在前面
减少了字典树的搜索空间，使得前缀能进行复用，同时{用于拼接，直接建立了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);
    }
};

这篇关于LeetCode/前缀和后缀搜索（字典树）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！