字典树的运用

前缀树 Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串,单词查找树,多叉树结构/

给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。

连接词 定义为：一个完全由给定数组中的至少两个较短单词组成的字符串。

这道题的题目第一想法就是字典树.字典树和深度遍历可以解决

class Solution {

    private Node root=new Node();//封装定义树的节点创建对象

    public List findAllConcatenatedWordsInADict(String[] words) {

Listans=new ArrayList<>();

Arrays.sort(words,(a,b)->a.length()-b.length());//将单词排序入集合里

for(String word:words){//分开单词放入单词组里

    if(!word.isEmpty()){

        if(dfs(word,0)){

            ans.add(word);

        }else{//不为连接词则放入单词树

            insert(word);

        }

    }

}

return ans;

    }

    private void insert(String word){

        Node node=this.root;

        for(int i=0;i

            if(node.children[word.charAt(i)-'a']==null){

                node.children[word.charAt(i)-'a']=new Node();//不能分割,建立新的节点集

            }

            node=node.children[word.charAt(i)-'a'];

        }

        node.isEnd=true;//能分割,得到的节点单词为true

    }

    private boolean dfs(String word,int i){

        if(i==word.length()){

            return true;}

            Node node=this.root;

while(i

        if(node.children[word.charAt(i)-'a']==null){

            return false;//不能出现只存在一个单词

        }

        node=node.children[word.charAt(i)-'a'];

        if(node.isEnd&&dfs(word,i+1)){

            return true;//形成完整单词,深入下一层

        }

        i++;

    }

    return false;

}

class Node{

    boolean isEnd;

    Node[]children;

    Node(){

        this.isEnd=false;//用boolea定义NODE的节点调用

        this.children=new Node[26];//子节点是新的26位

    }

}}