Java | solution using Trie Data Structure


  • 0
    M
    public class Solution {
        
        public String replaceWords(List<String> dict, String sentence) {
            
            Trie trie = new Trie();
            
            for (String s : dict) {
                trie.insert(s);
            }
            
            String[] sen = sentence.split(" +");
            
            for (int i = 0; i < sen.length; i++) {
                String root = trie.findRoot(sen[i]);
                if (!root.equals("")) {
                    sen[i] = root;
                }
            }
            
            StringBuilder result = new StringBuilder();
            
            for (String s : sen) {
                result.append(s + " ");
            }
    
            return result.substring(0, result.length() - 1).toString();
            
        }
    }
    
    class Trie {
        
        Map<Character, Trie> children;
        boolean endOfWord;
        
        // Will always store the root of the tree
        Trie root;
    
        public Trie() {
            this.children = new HashMap<Character, Trie>();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            
            if (root == null) {
                root = new Trie();
            }
            
            Trie node = root;
            
            for (char c : word.toCharArray()) {
                
                if (node.children.containsKey(c)) {
                    node = node.children.get(c);               
                } else {
                    // Create a new Trie Node
                    Trie newNode = new Trie();
                    
                    // Add the character at this node
                    node.children.put(c, newNode);
                    node = newNode;
                }
            }
            
            node.endOfWord = true;
        }
        
        public String findRoot(String word) {
            
            Trie node = root;
            
            StringBuilder rootWord = new StringBuilder("");
            
            for (char c : word.toCharArray()) {            
                node = node.children.get(c);
                if (node != null) {
                    rootWord.append(String.valueOf(c));
                    if (node.endOfWord) 
                        return rootWord.toString();
                } else if (node == null) {
                    break;
                }
            }
            
            return "";
        }    
    }
    

Log in to reply
 

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