Google 面试题分析 | 字典里面的最长单词

package trie;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;


public class Solution {

    class Trie {
        //待构建的字符串列表
        private String words[];
        private Node root;
        
        public Trie(String[] words){
            this.root=new Node();
            this.words=words;
        }
        public Node builtTrie(){
            int index=0;
            for (int i=0;i<words.length;i++){
                insert(words[i],++index);
            }
            return root;
        }
        /**
         *@param index表示在words数组中的索引,方便在trie节点中快速获取该单词
         */
        public void insert(String word,int index){
            if(word==""||word==null){
                return;
            }
            Node cur=root;
            char [] chars=word.toCharArray();
            for(int i=0;i<chars.length;i++){
                //如果不存在该值,则创建新节点
                char val=chars[i];
                if(!cur.getChildrens().containsKey(val)){
                    Node newNode=new Node();
                    newNode.setVal(val);
                    cur.getChildrens().put(val, newNode);
                }
                //如果已经存在则pass
                cur=cur.getChildrens().get(val);
            }
            cur.setEnd(index);
            
        }
        
       public  String DFS(){
            String result="";
            Stack<Node> stack=new Stack<Node>();
            stack.push(root);
            while(!stack.isEmpty()){
                Node node=stack.pop();
                if(node.getEnd()>0||node==root){
                    if(node!=root){
                        String word= this.words[node.getEnd()-1];
                        if(word.length()>result.length()||
                                word.length()==result.length()&&result.compareTo(word)>0){//最长的且具有最小字典序的word
                            result=word;
                        }
                    }
                    for(Node n:node.getChildrens().values()){//拿到子节点
                        stack.push(n);
                    }
                }
            }
            return result;
            
        }
    }
       
    class Node {
        // 节点字符值
        private char val;
        // 节点的子节点,即以根节点到该节点的值组成的字符串为前缀的字符串构建的节点
        private Map<Character, Node> childrens = new HashMap<Character, Node>();
        // 是否为结束节点,即一个字符串是否到达末尾节点 当end>0时表示结束节点  该节点存储单词在words列表中的位置
        private int end = 0;
       
        public char getVal() {
            return val;
        }

        public void setVal(char val) {
            this.val = val;
        }

        public Map<Character, Node> getChildrens() {
            return childrens;
        }

        public void setChildrens(Map<Character, Node> childrens) {
            this.childrens = childrens;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }
    }

   
   
    public static void main(String[] args) {
        String[] words=new String[]{"a", "banana", "app", "appl", "ap", "apply", "apple"};
        //String[] words=new String[]{"w","wo","wor","worl", "world"};
        Solution s=new Solution();
        Trie t=s.new Trie(words);
        t.builtTrie();
        System.out.println( t.DFS());  
         
     }
}