648. Replace Words

Link

Solution

  public class Trie{
        
        public Trie[] children;
        public char c;
        public boolean isPrefix;
        public Trie(char c){
            this.c = c;
            children = new Trie[26];
        }
    }
    
    
    
    public String replaceWords(List<String> dictionary, String sentence) {
        Trie root = new Trie(' ');
        
        for(String dic : dictionary){
            Trie it = root;
            for(int i = 0; i < dic.length(); i++){
                char c = dic.charAt(i);
                if(it.children[c-'a'] == null){
                    it.children[c-'a'] = new Trie(c);
                }
                it = it.children[c-'a'];
            }
            it.isPrefix = true;
        }
        String[] words = sentence.split(" ");
        String ret= "";
        for(String word : words){
            String replace = findReplacement(word, root);
            ret += replace + " ";
        }
        
        return ret.substring(0, ret.length()-1);
        
    }
    
    
    
    public String findReplacement(String word, Trie root){
        Trie it = root;
        for(int i = 0; i < word.length(); i++){
            if(it.isPrefix) return word.substring(0,i);
            char c = word.charAt(i);
            if(it.children[c-'a'] != null){
                it = it.children[c-'a'];
            }
            else{
               break;
            }
        }
        return word;
    }