2021-12-28 前缀树+472 连接词

前缀树： 定义一个类，包含两部分，一个子数组children和一个布尔类型isEnd·；子数组作指针表示字符存在，isEnd表示字符串是否到了结。

实现前缀树
java版本：

class Trie {

    /** Initialize your data structure here. */
    private Trie[] children;
    private boolean isEnd;
    public Trie() {
      
   children=new Trie[26];
   isEnd=false;
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
Trie node=this;
for(int i=0;i<word.length();i++){
    int index=word.charAt(i)-'a';

    if(node.children[index]==null){
        node.children[index]=new Trie();
    }
    node=node.children[index];
    
}
node.isEnd=true;
        
    
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
     Trie  node=  searchFix(word);
   return node!=null && node.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return searchFix(prefix)!=null;

    }

    public Trie searchFix(String word){
   Trie node=this;
        for(int i=0;i<word.length();i++){
            int index=word.charAt(i)-'a';
            if(node.children[index]==null){
                  return null;
            }
            node=node.children[index];

        }
        return node;

    }
}

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

连接词：// 根据String数组，找到长的单词，这个长的单词 包含数组内多个短的词
先对数组进行按长度排序，接着遍历String数组，利用前缀树，执行DFS，判定是否该字符串包含两个前缀树插入的字符串。
java版本：

class Solution {
    Trie trie=new Trie();
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
//   找到长的 包含多个短的词
Arrays.sort(words,(a,b)->a.length()-b.length());
    List<String> ans=new ArrayList<String>();
    for(int i=0;i<words.length;i++){
     String   word=words[i];
      if (word.length() == 0) {
                continue;
            }
     if(dfs(word,0)){
          ans.add(word);
     }else{
         insert(word);
     }
    }
    

return ans;
    }
    public boolean dfs(String word,int start){
     if (word.length() == start) {
            return true;
        }
        Trie node=trie;
        for(int i=start;i<word.length();i++){
            int index=word.charAt(i)-'a';
              node=node.children[index];
            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++){
            int index=word.charAt(i)-'a';
            if(node.children[index]==null){
                node.children[index]=new Trie();
            }
            node=node.children[index];
        }
        node.isEnd=true;
    }
}
class Trie{
    public Trie[] children;
    public boolean isEnd;
    public Trie(){
        children=new Trie[26];
        isEnd=false;
    }
}