[brother hero July training] day 23: dictionary tree

---

One 、1032. Character stream

1032. Character stream

Design an algorithm ： Receive a character stream , And check whether the suffix of these characters is a string array words A string in .
for example ,words = [“abc”, “xyz”] And the character stream is added one by one 4 Characters ‘a’、‘x’、‘y’ and ‘z’ , The algorithm you designed should be able to detect “axyz” The suffix “xyz” And words String in “xyz” matching .
According to the following requirements StreamChecker class ：
StreamChecker(String[] words) ： Constructors , Use a string array words Initialize data structure .
boolean query(char letter)： Receive a new character from the character stream , If any non empty suffix in the character stream can match words A string in , return true ; otherwise , return false.

leetcode1032 java

Ideas

Construct a dictionary tree ( Whether the leaf node \next)

initialization , Here, the incoming characters are written into the dictionary tree in reverse order , Such as "cd", “f”, “kl”, Write as dcflk

To find the character , Write the first node every time , Such as query a,b,c,d by lookup dcba , from d Start looking for , And if the leaf node , return true, That is to dc Medium c It's about , Meet the conditions , return true

class StreamChecker {
    
    public class TrieNode{
    
        boolean isleaf;
        TrieNode[] next;
        public TrieNode(){
    
            next = new TrieNode[26];
        }
    }
    public void insert(String word){
    
        if(word==null||word.length()==0) return;
        TrieNode node = root;
        for(int i =0;i<word.length();i++){
    
            char c = word.charAt(i);
            TrieNode temp = node.next[c-'a'];
            if(temp==null){
    
                temp = new TrieNode();
                node.next[c-'a']=temp;
            }
            node = node.next[c-'a'];
        }
        node.isleaf = true;
    }
    int maxlength = 0;
    TrieNode root;
    StringBuilder stream = new StringBuilder();


    public StreamChecker(String[] words) {
    
        root = new TrieNode();
        for(String word:words){
    
            maxlength = Math.max(maxlength,word.length());
            insert(new StringBuilder(word).reverse().toString());
        }
        
    }
    
    public boolean query(char letter) {
    
        stream.insert(0,letter);
        if(stream.length()>maxlength) stream.deleteCharAt(stream.length()-1);
        TrieNode temp = root;
        for(int i = 0;i<stream.length();i++){
    
            if(temp.next[stream.charAt(i)-'a']==null) return false;
            temp = temp.next[stream.charAt(i)-'a'];
            if(temp.isleaf) return true;
        }
        return temp.isleaf;

    }


}

---

summary