Java Solution using Trie


  • 0
    F
    class Solution {
        private static class TrieNode {
            public boolean isEnd = false;
            public Map<Character, TrieNode> children = new HashMap<>();
        }
        
        private static class Trie {
            private TrieNode root = new TrieNode();
            
            public void add(String w) {
                if(w!=null && w.length()>0) {
                    TrieNode node = root;
                
                    for(int idx = 0; idx < w.length(); idx++) {
                        TrieNode next = node.children.get(w.charAt(idx));
                        if(next == null) {
                            node.children.put(w.charAt(idx), next = new TrieNode());
                        } 
                        node = next;
                    }
                    node.isEnd = true;
                }
            }
            
            public String rootOf(String w) {
                if(w==null || w.length()==0) {
                    return null;
                } else {
                    return rootOf(w, 0, root, new StringBuilder());
                }
            }
            
            private String rootOf(String w, int curIdx, TrieNode node, StringBuilder rootSb) {
                if(node==null || curIdx==w.length()) {
                    return null;
                } else if(node.isEnd) {
                    return rootSb.toString();
                } else {
                    return rootOf(w, curIdx+1, node.children.get(w.charAt(curIdx)), rootSb.append(w.charAt(curIdx)));
                }
            }
        }
        
        public String replaceWords(List<String> dict, String sentence) {
            StringBuilder sb = new StringBuilder();
            String[] words = sentence.split(" ");
            Trie trie = new Trie();
            
            for(String root:dict) {
                trie.add(root);
            }
            for(String w:words) {
                String root = trie.rootOf(w);
                
                if(root == null) {
                    sb.append(w).append(" ");
                } else {
                    sb.append(root).append(" ");
                }
            }
            
            return sb.substring(0, sb.length()-1);
        }
    }
    

    Here is a iterative version of rootOf():

    public String rootOf(String w) {
            if(w==null || w.length()==0) {
                return null;
            } else {
                TrieNode node = root;
                StringBuilder sb = new StringBuilder();
                    
                for(int idx = 0; idx < w.length(); idx++) {
                    TrieNode next = node.children.get(w.charAt(idx));
                      
                    if(next == null) {
                        break;
                    } else {
                        sb.append(w.charAt(idx));
                        if(next.isEnd) {
                            return sb.toString();
                        } else {
                            node = next;
                        }
                    }
                }
                    
                return null;
            }
        }
    

Log in to reply
 

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