Java easy to understand Trie solution


  • 0
    F
    class Solution {
        class TrieNode {
            TrieNode[] children;
            boolean isWord;
            String word;
            public TrieNode() {
                children = new TrieNode[26];
                isWord = false;
                word = "";
            }
        }
        public TrieNode buildTrie(List<String> words) {
            TrieNode root = new TrieNode();
            for (String s : words) {
                TrieNode node = root;
                for (char c : s.toCharArray()) {
                    if (node.children[c - 'a'] == null) {
                        node.children[c - 'a'] = new TrieNode();
                    }
                    node = node.children[c - 'a'];
                }
                node.isWord = true;
                node.word = s;
            }
            return root;
        }
        public String replaceWords(List<String> dict, String sentence) {
            if (dict == null || dict.size() == 0) {
                return sentence;
            }
            TrieNode root = buildTrie(dict);
            String[] parts = sentence.trim().split("\\s+");
            for (int i = 0; i < parts.length; i++) {
                TrieNode node = root;
                for (char c : parts[i].toCharArray()) {
                    if (node.children[c - 'a'] == null) {
                        break;
                    }
                    node = node.children[c - 'a'];
                    if (node.isWord) {
                        parts[i] = node.word;
                        break;
                    }
                }
            }
            return String.join(" ", parts);
        }
    }
    

Log in to reply
 

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