Java Trie solution beat 100%


  • -1

    For each word in the dictionary we insert it into the Trie. For each word in the sentence we search along the Trie to find the earliest point it match a word from the dictionary.

        class TrieNode {
            private TrieNode[] children;
            private boolean isWord;
            private String content;
            public TrieNode() {
                children = new TrieNode[26];
                isWord = false;
            }
        }
    
        private TrieNode root = new TrieNode();
    
        private void addWord(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i)-'a';
                if (cur.children[index] == null) cur.children[index] = new TrieNode();
                cur = cur.children[index];
            }
            cur.isWord = true;
            cur.content = word;
        }
    
        public String replaceWords(List<String> dict, String sentence) {
            for (String word : dict) {
                addWord(word);
            }
            String[] strs = sentence.split("\\s+");
            StringBuilder sb = new StringBuilder();
            for (String s : strs) {
                TrieNode cur = root;
                boolean matched = false;
                for (int i = 0; i < s.length(); i++) {
                    int index = s.charAt(i)-'a';
                    if (cur.children[index] == null) break;
                    cur = cur.children[index];
                    if (cur.isWord) {
                        matched = true;
                        break;
                    }
                }
                if (sb.length() > 0) sb.append(" ");
                sb.append(matched ? cur.content : s);
            }
            return sb.toString();
        }
    

Log in to reply
 

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