Java Simple/Classical Trie question/solution (Beat 96%)


  • 15
    public String replaceWords(List<String> dict, String sentence) {
            String[] tokens = sentence.split(" ");
            TrieNode trie = buildTrie(dict);
            return replaceWords(tokens, trie);
        }
    
        private String replaceWords(String[] tokens, TrieNode root) {
            StringBuilder stringBuilder = new StringBuilder();
            for (String token : tokens) {
                stringBuilder.append(getShortestReplacement(token, root));
                stringBuilder.append(" ");
            }
            return stringBuilder.substring(0, stringBuilder.length()-1);
        }
    
        private String getShortestReplacement(String token, final TrieNode root) {
            TrieNode temp = root;
            StringBuilder stringBuilder = new StringBuilder();
            for (char c : token.toCharArray()) {
                stringBuilder.append(c);
                if (temp.children[c - 'a'] != null) {
                    if (temp.children[c - 'a'].isWord) {
                        return stringBuilder.toString();
                    }
                    temp = temp.children[c - 'a'];
                } else {
                    return token;
                }
            }
            return token;
        }
    
        private TrieNode buildTrie(List<String> dict) {
            TrieNode root = new TrieNode(' ');
            for (String word : dict) {
                TrieNode temp = root;
                for (char c : word.toCharArray()) {
                    if (temp.children[c - 'a'] == null) {
                        temp.children[c - 'a'] = new TrieNode(c);
                    }
                    temp = temp.children[c - 'a'];
                }
                temp.isWord = true;
            }
            return root;
        }
    
        public class TrieNode {
            char val;
            TrieNode[] children;
            boolean isWord;
    
            public TrieNode(char val) {
                this.val = val;
                this.children = new TrieNode[26];
                this.isWord = false;
            }
        }
    

    Also viewable on Github here.


  • 0

    Great solution! And you can simply combine the first two replaceWords together...


  • 1
    F

    Same idea

    public class Solution {
        public class TrieNode{
            boolean isWord;
            TrieNode[] next;
            public TrieNode(){
                next = new TrieNode[26];
            }
        }
        
        TrieNode root = new TrieNode();
        
        public void add(String word){
            TrieNode cur = root;
            for(int i = 0;i<word.length();i++){
                int c = word.charAt(i)-'a';
                if(cur.next[c] == null){
                    cur.next[c] = new TrieNode();
                }
                cur = cur.next[c];
            }
            cur.isWord = true;
        }
        
        public String findRoot(String word){
            TrieNode cur = root;
            int i = 0;
            for(;i<word.length();i++){
                int c = word.charAt(i)-'a';
                if(cur.next[c] == null){
                    return word;
                }
                if(cur.next[c].isWord){
                    return word.substring(0,i+1);
                }
                cur = cur.next[c];
            }
            return word;
        }
        
        public String replaceWords(List<String> dict, String sentence) {
            for(int i = 0;i<dict.size();i++){
                add(dict.get(i));
            }
            String[] str = sentence.split(" ");
            for(int i = 0;i<str.length;i++){
                str[i] = findRoot(str[i]);
            }
            return String.join(" ",str);
        }
    }
    

  • 2
    H

    One optimization is when building the trie, if a shorter root is already found, we can stop adding it to the trie. e.g. "a", "aa", "aaa", if "a" is already in the trie, we don't need to go beyond first character of "aa" and "aaa".


  • 0
    X

    Instead of using boolean isWord as a trie node filed, you can use String word as in Word Search 2.


  • 0
    W

    Similar idea,but it is easy to understand and beats 91.1%.

    class TrieNode {
            final static int SIZE = 26;
            char val;
            TrieNode[] children;
            boolean isWord;
    
            public TrieNode(char val) {
                this.val = val;
                children = new TrieNode[SIZE];
            }
        }
    
        TrieNode root = new TrieNode(' ');
    
        private void addWord(String word) {
            TrieNode current = root;
            for (char c : word.toCharArray()) {
                TrieNode next = current.children[c - 'a'];
                if (next == null) {
                    current.children[c - 'a'] = new TrieNode(c);
                    next = current.children[c - 'a'];
                }
                current = next;
            }
            current.isWord = true;
        }
    
        private String findRoot(String word) {
            TrieNode current = root;
            StringBuilder res = new StringBuilder();
            for (char c : word.toCharArray()) {
                TrieNode next = current.children[c - 'a'];
                if (next == null) {
                    break;
                }
                res.append(c);
                current = next;
                if (current.isWord == true) {
                    return res.toString();
                }
            }
            return word;
        }
    
    
        public String replaceWords(List<String> dict, String sentence) {
            for (String s : dict) {
                addWord(s);
            }
            String[] tokens = sentence.split(" ");
            for (int i = 0; i < tokens.length; i++) {
                tokens[i] = findRoot(tokens[i]);
            }
            return String.join(" ", tokens);
        }
    

  • 0

Log in to reply
 

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