当前位置：网站首页>【英雄哥六月集训】第 23天: 字典树

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

二、最长单词

面试题 17.15. 最长单词

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;

    }
}