当前位置：网站首页>[brother hero June training] day 23: dictionary tree

Also known as word search tree ,Trie Trees , It's a tree structure , It's a variation of the hash tree . The typical application is for statistics , Sort and save a lot of strings （ But it's not just about strings ）, So it is often used in text word frequency statistics by search engine system . Its advantages are ： Use the public prefix of the string to reduce query time , Minimize unnecessary string comparisons , Query efficiency is higher than hash tree .

One 、 Conjunctions

472. Conjunctions

class Solution {
    
    class Trie{
    
        Trie[] children;
        boolean isEnd;
        public Trie(){
    
            children = new Trie[26];
            isEnd = false;
        }
    }
    Trie trie= new Trie();
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
    
        List<String> ans = new ArrayList<String>();
        Arrays.sort(words,(a,b)->a.length()-b.length());
        for(int i=0; i< words.length; i++){
    
            String word = words[i];
            if(word.length()==0){
    
                continue;
            }
            boolean[] visited = new boolean[word.length()];
            if(dfs(word,0,visited)){
    
                ans.add(word);
            } else {
    
                insert(word);
            }
        }
        return ans;

    }

    public boolean dfs(String word,int start,boolean[] visited){
    
        if(word.length() == start){
    
            return true;
        }
        if(visited[start]){
    
            return false;
        }
        visited[start] = true;
        Trie node = trie;
        for( int i=start; i<word.length(); i++){
    
            char ch = word.charAt(i);
            int index = ch - 'a';
            node = node.children[index];
            if(node == null){
    
                return false;
            }
            if(node.isEnd){
    
                if(dfs(word,i+1,visited)){
    
                    return true;
                }
            }
        }
        return false;
    }
    public void insert(String word){
    
        Trie node = trie;
        for(int i = 0;i<word.length();i++){
    
            char ch=word.charAt(i);
            int index = ch -'a';
            if(node.children[index]==null){
    
                node.children[index]= new Trie();
            }
            node = node.children[index];
        }
        node.isEnd=true;
    }
}

Two 、 The longest word

Interview questions 17.15. The longest word

class Solution {
    
    class Trie{
    
        Trie[] children;
        boolean isEnd;
        public Trie(){
    
            children = new Trie[26];
            isEnd = false;
        }
    }
    Trie trie= new Trie();

    public boolean dfs(String word,int start){
    
        
        
        Trie node = trie;
        if(word.length() == start){
    
            return true;
        }
        
        for(int i=start;i<word.length();i++){
    
            int c=word.charAt(i)-'a';
            node=node.children[c];
            if(node == null) return false;
            if(node.isEnd){
    
                if(dfs(word,i+1)){
    
                    return true;
                }
            }
        }
        return false;
    }
    public void insert(String word){
    
        Trie node = trie;
        for(int i = 0;i<word.length();i++){
    
            char ch=word.charAt(i);
            int index = ch -'a';
            if(node.children[index]==null){
    
                node.children[index]= new Trie();
            }
            node = node.children[index];
        }
        node.isEnd=true;
    }
    public String longestWord(String[] words) {
    
        String ret="";
        Arrays.sort(words,(o1,o2)->o1.length()-o2.length());
        for(String word:words){
    
            if(word.length()==0) continue;
            if(dfs(word,0)){
    
                if(ret.length()<word.length()){
    
                    ret=word;
                } else if(ret.length()==word.length()){
    
                    if(ret.compareTo(word)>0){
    
                        ret = word;
                    }
                }
            }
            else{
    
                insert(word);
            }
        }

        
        return ret;

    }
}

summary

getOrDefault(Object key, V defaultValue)
It means when Map There's this in the collection key when , Just use this key Corresponding value value , If not, use the default value defaultValue

原网站

版权声明
本文为[If I were Wen Shuai]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/208/202207271001017111.html