Java Solution Beats 90%


  • 0
    S
    class Solution {
        private class TrieNode {
            public TrieNode[] next;
            public boolean isWord;
            public TrieNode() {
                this.next = new TrieNode[26];
            }
        }
        
        private TrieNode root;
        
        public String replaceWords(List<String> dict, String sentence) {
            root = new TrieNode();
            for (String word : dict) {
                this.insert(word);
            }
            
            String[] tokens = sentence.split(" ");
            StringBuilder sb = new StringBuilder();
            for (String token : tokens) {
                sb.append(replace(token));
                sb.append(" ");
            }
            
            return sb.toString().trim();
        }
        
        private String replace(String word) {
            TrieNode node = root;
            StringBuilder sb = new StringBuilder();
            
            for (char c : word.toCharArray()) {
                if (node.next[c - 'a'] == null) {
                    return word;
                }
                
                sb.append(c);
                node = node.next[c - 'a'];
                if (node.isWord) break;
            }
                
            return sb.toString();
        }
        
        private void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (node.next[c - 'a'] == null) {
                    node.next[c - 'a'] = new TrieNode();
                }
                
                node = node.next[c - 'a'];
            }
            
            node.isWord = true;
        }
    }
    
    

Log in to reply
 

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