Easy understand java solution, Trie


  • 0
    D
    class TrieNode {
        TrieNode[] child = new TrieNode[26];
        String word;
        public TrieNode() {
            word = "";
        }
    }
    
    class TrieTree {
        public TrieNode root = new TrieNode();
        
        public TrieTree(List<String> words) {
            for(String word : words) {
                TrieNode p = root;
                for(char c : word.toCharArray()) {
                    if(p.child[c - 'a'] == null) {
                        p.child[c - 'a'] = new TrieNode();
                    }
                    p = p.child[c - 'a'];
                }
                p.word = word;
            }
        }
        
        public String getPrefix(String word) {
            TrieNode p = root;
            
            for(char c : word.toCharArray()) {
                if(p.child[c - 'a'] == null) {
                    return "";
                }
                
                p = p.child[c - 'a'];
                if(!p.word.equals("")) {
                    return p.word;
                }
            }
            
            return "";
        }
    }
    
    public String replaceWords(List<String> dict, String sentence) {
        TrieTree tr = new TrieTree(dict);
        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        
        for(int i = 0; i < words.length; i++) {
            String prefix = tr.getPrefix(words[i]);
            if(!prefix.equals("")) {
                sb.append(prefix);
            } else {
                sb.append(words[i]);
            }
            
            if(i < words.length - 1) {
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }

Log in to reply
 

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