Simple Java Solution Using Trie(Beat 98%)


  • 0
    F
    public class Solution {
        public class TrieNode{
            boolean isWord;
            TrieNode[] next;
            public TrieNode(){
                next = new TrieNode[26];
            }
        }
        
        TrieNode root = new TrieNode();
        
        public void add(String word){
            TrieNode cur = root;
            for(int i = 0;i < word.length();i++){
                int c = word.charAt(i) - 'a';
                if(cur.next[c] == null){
                    cur.next[c] = new TrieNode();
                }
                cur = cur.next[c];
            }
            cur.isWord = true;
        }
        
        public String findRoot(String word){
            TrieNode cur = root;
            int i = 0;
            for(;i < word.length();i++){
                int c = word.charAt(i) - 'a';
                if(cur.next[c] == null){
                    return word;
                }
                if(cur.next[c].isWord){
                    return word.substring(0,i + 1);
                }
                cur = cur.next[c];
            }
            return word;
        }
        
        public String replaceWords(List<String> dict, String sentence) {
            for(int i = 0;i < dict.size();i++){
                add(dict.get(i));
            }
            String[] str = sentence.split(" ");
            for(int i = 0;i < str.length;i++){
                str[i] = findRoot(str[i]);
            }
            return String.join(" ",str);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.