力扣——单词替换

import java.util.List;

class Solution {

    private class Trie{
        private boolean leaf;
        private Trie[] childs;

        public Trie() {
            this.childs = new Trie[26];
        }

        public boolean isLeaf() {
            return leaf;
        }

        public void setLeaf(boolean leaf) {
            this.leaf = leaf;
        }

        public Trie getChild(char c) {
            return childs[c- ‘a‘];
        }

        public Trie addChild(char c){
            Trie a = new Trie();
            childs[c - ‘a‘] = a;
            return a;
        }

        public Boolean hasChild(char c){
            if(childs[c-‘a‘] != null){
                return true;
            }
            return false;
        }

        public void addWord(String word){
            Trie now = this;
            if(word == null || word.isEmpty()){
                return;
            }
            for(char c : word.toCharArray()){
                if(now.hasChild(c)){
                    now = now.getChild(c);
                }else{
                    now = now.addChild(c);
                }
            }
            now.setLeaf(true);
        }

        public String getShortTestRoot(String word){
            String res = "";
            if(word == null || word.isEmpty()){
                return res;
            }
            Trie now = this;
            for(char c : word.toCharArray()){
                if(now.hasChild(c)){
                    now = now.getChild(c);
                    res += c;
                    if(now.isLeaf()){
                        return res;
                    }
                }else{
                    break;
                }
            }
            return "";
        }
    }

    public String replaceWords(List<String> dict, String sentence) {
        Trie root = new Trie();
        for(String w : dict){
            root.addWord(w);
        }
        String[] dep = sentence.split(" ");
        for(int i = 0; i< dep.length; i++){
            String change = root.getShortTestRoot(dep[i]);
            if(!change.isEmpty()){
                dep[i] = change;
            }
        }
        return String.join(" ", dep);
    }
}