Solution using Trie. Beats >96% in Java.


  • 0
    public class Solution {
        
        private class Trie {
            TrieNode head;
            
            public Trie() {
                this.head = new TrieNode('\0');
            }
            
            public void insert(String word) {
                TrieNode currentNode = head;
                
                for (char c : word.toCharArray()) {
                    if (currentNode.children[c - 'a'] == null) currentNode.children[c - 'a'] = new TrieNode(c);
                    currentNode = currentNode.children[c - 'a'];
                }
                
                currentNode.isWord = true;
                currentNode.word = word;
            }
            
            public void print() {
                print(head);
            }
            
            public void print(TrieNode node) {
                if (node == null) return;
                
                if (node.isWord) System.out.println(node.word);
                
                for (TrieNode child : node.children) {
                    print(child);
                }
            }
        }
        
        private class TrieNode {
            char val;
            boolean isWord;
            String word;
            TrieNode[] children;
            
            public TrieNode(char val) {
                this.val = val;
                this.children = new TrieNode[26];
                this.isWord = false;
            }
        }
        
        public String replaceWords(List<String> dict, String sentence) {
            Trie trie = new Trie();
            
            for (String word : dict) {
                trie.insert(word);
            }
            
            StringBuilder sb = new StringBuilder();
            String[] split = sentence.split(" ");
            
            for (int i = 0; i < split.length; i++) {
                String word = split[i];
                TrieNode currentNode = trie.head;
                
                for (int j = 0; j < word.length() && currentNode != null && !currentNode.isWord; j++) {
                    char c = word.charAt(j);
                    currentNode = currentNode.children[c - 'a'];
                }
                
                if (currentNode == null || !currentNode.isWord) sb.append(word);
                else sb.append(currentNode.word);
                
                if (i < split.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.