Use of dictionary tree

 

Catalog

208. Realization Trie ( Prefix tree )

648. Word substitution

676. Implement a magic dictionary

720. The longest word in the dictionary

211. Add and search words - Data structure design

---

208. Realization Trie ( Prefix tree )

Trie（ It sounds like "try"） Or say Prefix tree It's a tree data structure , Keys for efficient storage and retrieval of string datasets . This data structure has quite a number of application scenarios , For example, automatic completion and spelling check .

Please realize Trie class ：

Trie() Initialize the prefix tree object .
void insert(String word) Insert a string into the forward tree word .
boolean search(String word) If the string word In the prefix tree , return true（ namely , Has been inserted before retrieval ）; otherwise , return false .
boolean startsWith(String prefix) If a string has been inserted before  word One of the prefixes of is prefix , return true ; otherwise , return false .

 

class Trie {
private:
    Trie* children[26]={nullptr};
    bool isEnd=false;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() {}
    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {// If there is no index corresponding to the current letter   Generate a new structure   And let the current index point to the next structure 
                node->children[ch] = new Trie();
            }
            node = node->children[ch];// The pointer points to the last position of the structure 
        }
        node->isEnd = true;// When no more letters are inserted   Of the last structure of the tree structure children All indexes of the table are nullptr  And let the end sign be true
    }

    bool search(string word) {// Determine whether there are words 
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {// Determine whether there is a prefix 
        Trie* node = this->searchPrefix(prefix);
        return node != nullptr;// There is no need to judge the difference node->isEnd Whether it is the end of the word 
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

648. Word substitution

In English , We have one called   Root (root) The concept of , You can add other words after the root to form another longer word —— We call it   Inheritance words (successor). for example , Root an, Follow the word  other( other ), Can form new words  another( the other one ).

Now? , Given a dictionary consisting of many roots dictionary And a sentence formed by separating words with spaces sentence. You need to replace all the inherited words in the sentence with roots . If an inherited word has many roots that can form it , Replace it with the shortest root .

You need to output the replaced sentences .

Example 1：

Input ：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output ："the cat was rat by the bat"

class Trie{
private:
    bool isEnd = false;
    Trie* next[26] = {nullptr};
public:
    Trie(){}

    void insert(const string &word){
        Trie* node=this;
        for(auto c:word){
            if(node->next[c-'a']==nullptr){
                node->next[c-'a']=new Trie();
            }
            node=node->next[c-'a'];// not node=node->next;
        }
        node->isEnd=true;
    }

    string findRoot(const string &word){
        Trie* node=this;
        string result;
        for(auto c:word){
            if(node->next[c-'a']){
               result+=c;
               node=node->next[c-'a'];
               if(node->isEnd){
                   return result;
               }
            }
            else return word;
        }
        return word;
    }
};

class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        Trie* tree = new Trie();
        for(auto root:dictionary){
            tree->insert(root);
        }
        istringstream sin(sentence);
        string ans = "";
        string word;
        while(sin>>word){
            ans += tree->findRoot(word) + " ";
        }
        return ans.substr(0, ans.size()-1);
    }
};

istringstream Use Included in sstream Header file （ Input stream of string ）

676. Implement a magic dictionary

Design a data structure initialized with word list , Words in the word list Different from each other . If you give a word , Please decide whether you can replace only one letter of this word with another , Make the formed new words exist in the dictionary you build .

Realization MagicDictionary class ：

MagicDictionary() Initialize object
void buildDict(String[] dictionary) Use string arrays  dictionary Set the data structure ,dictionary Strings in are different from each other
bool search(String searchWord) Given a string searchWord , Determine whether you can only put... In the string One Replace one letter with another , So that the new string formed can match any string in the dictionary . If possible , return true ; otherwise , return false .

class MagicDictionary {
private:
    bool isEnd=false;
    MagicDictionary* next[26]={nullptr};
public:
    MagicDictionary() {
    }
    
    void buildDict(vector<string> dictionary) {

        for(auto word:dictionary){
            MagicDictionary* node=this;
            for(auto c:word){
            if(node->next[c-'a']==nullptr){
                node->next[c-'a']=new MagicDictionary();
            }
            node=node->next[c-'a'];
        }
        node->isEnd=true;
        }

    }
    bool dfs(MagicDictionary* node,string word,int index,bool diff){
        // if(node==nullptr) return false;
        if(index==word.size()){
            return diff&&node->isEnd;// There are letters that have been changed and are the end of the word 
        }
        char c=word[index];
        int i=c-'a';
        // int i = word[index] - 'a';
        if(node->next[c-'a']!=nullptr){
            if(dfs(node->next[c-'a'],word,index+1,diff)) return true;
        }
         
        if(!diff){// If you need to change the letters   Match the remaining letters except the current letter   It can only be changed once   So the following diff All are true It means that it has been changed 
            for(int j=0;j<26;j++){
                if(j!=i&&node->next[j]!=nullptr){
                    if(dfs(node->next[j],word,index+1,true)) return true ;//diff Set to true  It means that some letters have been changed 
                   // if(dfs(node->next[i],word,index+1,true)) return true ;//!!!j It has been written. i  The day 
                }
            }
        }
        return false;
    }

    bool search(string dfsWord) {
        MagicDictionary* node=this;
        return dfs(node,dfsWord,0,false);
    }
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dictionary);
 * bool param_2 = obj->dfs(dfsWord);
 */

720. The longest word in the dictionary

Give an array of strings  words A dictionary of English . return  words The longest word in , The word is created by  words  Other words in the dictionary gradually add a letter to form .

If there are more than one possible answer , The word with the smallest dictionary order in the answer is returned . If there is no answer , Returns an empty string .

Example 1：

Input ：words = ["w","wo","wor","worl", "world"]
Output ："world"
explain ： word "world" May by "w", "wo", "wor", and "worl" Gradually add a letter to form .
Example 2：

Input ：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output ："apple"
explain ："apply" and "apple" Can be composed of words in the dictionary . however "apple" The dictionary order of is less than "apply" 

class Trie{
private:
    Trie* next[26]={nullptr};
    bool isEnd=false;
public:
    Trie(){}
void insert(string &word){
    Trie* node=this;
    for(auto c:word){
        if(node->next[c-'a']==nullptr){
            node->next[c-'a']=new Trie();
        }
        node=node->next[c-'a'];
    }
    node->isEnd=true;// After the insertion, the end flag needs to be assigned 
}
bool isword(string &word){
    Trie* node=this;
    for(auto c:word){
        if(node->next[c-'a']==nullptr||node->next[c-'a']->isEnd==false){// Any prefix of a word needs to be satisfied in the dictionary   So we must have more node->next[c-'a']->isEnd==false This judgment   It means to judge whether this letter is the ending letter   by false Indicates not to end   That is, it is not a prefix word  
        //apple  If only this word is inserted   After that e Corresponding siEnd It's just true  This is the time apple Will not meet the requirements ！！！ But if there are words inserted a,ap,app,appl, Then every word isEnd All for true 了   Only in this way can we meet the need to splice words one by one apple
           
            return false;
        }
        node=node->next[c-'a'];
    }
    return node&&node->isEnd==true;
}
};
class Solution {
public:
    string longestWord(vector<string>& words) {
        Trie T;
        for(auto word:words){
            T.insert(word);
        }
        string result;
        for(auto word:words){
            if(T.isword(word)){
                if(word.size()>result.size()){
                    result=word;
                }
                else if(word.size()==result.size()&&word<result){
                    result=word;
                }
            }
        }
        return result;
    }
};

211. Add and search words - Data structure design

Please design a data structure , Support Add new words and Find whether the string matches any previously added string .

Implement dictionary class WordDictionary ：

WordDictionary() Initialize dictionary object
void addWord(word) take word Add to the data structure , Then you can match it
bool search(word) If there is a string and  word matching , Then return to true ; otherwise , return   false .word There may be some '.' , Every  . Can represent any letter .

class WordDictionary {
private:
    bool isEnd=false;
    WordDictionary* next[26]={nullptr};
public:
    WordDictionary() {}
    
    void addWord(string word) {
        WordDictionary* node=this;
        for(auto c:word){
            if(node->next[c-'a']==nullptr){
                node->next[c-'a']=new WordDictionary();
            }
            node=node->next[c-'a'];
        }
        node->isEnd=true;
    }
    bool dfs(string word,int index,WordDictionary* node){
        // if(node==nullptr) return false;
        if(index==word.size()){
            return node->isEnd;
        }
        char c=word[index];
        if(c=='.'){// If the current bit "." You need to go back   use 26 Replace any one of them  
            for(int i=0;i<26;i++){
                if(node->next[i]&&dfs(word,index+1,node->next[i])) return true;
                // At first, it was written directly return dfs(word,index+1,node->next[i])  Missing possible true
            }
        }
        else{
            return node->next[c-'a']&&dfs(word,index+1,node->next[c-'a']);
            //!!!! stay dfs(word,index+1,node->next[i]) and dfs(word,index+1,node->next[c-'a']
            // with node->next[i] and  node->next[c-'a'] There will be no overtime ！！！！ If the next one is empty, then there is no need dfs 了   It's equivalent to pruning 
        }
        return false;
        // return false;
    }
    bool search(string word) {
        WordDictionary* node=this;
        return dfs(word,0,node);
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */