Simple Java 8 and Trie based solution


  • 7

    The only modification to the standard Trie, is that we need a function getShortestPrefix that returns the shortest prefix of the given word in the trie, if the shortest prefix exists or return the original word. Once we have this, all we have to do is iterate through the sentence and replace each word with the getShortestPrefix(word) in the trie.

    public String replaceWords(List<String> dict, String sentence) {
        Trie trie = new Trie(256);
        dict.forEach(s -> trie.insert(s));
        List<String> res = new ArrayList<>();
        Arrays.stream(sentence.split(" ")).forEach(str -> res.add(trie.getShortestPrefix(str)));
        return res.stream().collect(Collectors.joining(" "));
    }
    
    
    class Trie {
        private int R;
        private TrieNode root;
    
        public Trie(int R) {
            this.R = R;
            root = new TrieNode();
        }
    
        // Returns the shortest prefix of the word that is there in the trie
        // If no such prefix exists, return the original word
        public String getShortestPrefix(String word) {
            int len =  getShortestPrefix(root, word, -1);
            return (len < 1) ? word : word.substring(0, len);
        }
    
        private int getShortestPrefix(TrieNode root, String word, int res) {
            if(root == null || word.isEmpty()) return 0;
            if(root.isWord) return res + 1;
            return getShortestPrefix(root.next[word.charAt(0)], word.substring(1), res+1);
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            insert(root, word);
        }
    
        private void insert(TrieNode root, String word) {
            if (word.isEmpty()) { root.isWord = true; return; }
            if (root.next[word.charAt(0)] == null) root.next[word.charAt(0)] = new TrieNode();
            insert(root.next[word.charAt(0)], word.substring(1));
        }
    
        private class TrieNode {
            private TrieNode[] next = new TrieNode[R];
            private boolean isWord;
        }
    }
    

  • 5

    Similar idea with some optimization. 33ms.

    For words: a, ab, abc in dict, only need to add 'a' into the Trie. Since the words which are successor of ab and abc must also be successor of a and will return 'a' immediately when it go through the Trie and find out 'a' is a word in dict.

    public class Solution {
        private TrieNode root;
        
        public String replaceWords(List<String> dict, String sentence) {
            root = new TrieNode();
            for (String rootWord : dict) {
                root.add(rootWord, 0);
            }
            String[] words = sentence.split("\\s+");
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < words.length; i++){
                sb.append(root.getRootWord(words[i], 0));
                if (i != words.length -1) sb.append(" ");
            }
            return sb.toString();
        }
        
        class TrieNode{
            int length = 0; //equivalent to store the root word ends here (only nodes represent root word have lenght > 0)
            HashMap<Character, TrieNode> children;
            
            public TrieNode(){
                children = new HashMap<>();
            }
            //recursive add
            public void add(String str, int idx) {
                if (this.length != 0) return; //no need to add 'ab', 'abc' in dict to the trie, when 'a' has already been added
                else if (idx == str.length()) {
                    this.length = idx;
                    return;
                }
                char ch = str.charAt(idx);
                children.putIfAbsent(ch, new TrieNode());
                children.get(ch).add(str, idx+1); //recursive call
            }
            
            //recursive get
            public String getRootWord(String str, int idx){
                if(this.length != 0) return str.substring(0, length); // length != 0 means this node represent a root word
                else if (idx == str.length() || 
                         !children.containsKey(str.charAt(idx))) return str; //no match root word
                return children.get(str.charAt(idx)).getRootWord(str, idx+1); //recursive call
            }
        }
    }
    

  • 1

    @LeetCoding thats a good optimization, one possible issue in your implementation of Trie is, you are storing the entire word in the TrieNode that ends the word, this can be avoided as it defeats the space saving advantages of a Trie.


  • 0

    @johnyrufus16
    Thanks for the suggestion.


  • 1
    M

    Thanks for your Trie solution. The C++ version:

    class Solution {
    public:
        string replaceWords(vector<string>& dict, string sentence) {
            Trie trie(26);
            for(const string& word:dict) trie.insert(word);
            string result;
            for(size_t i=0; i<sentence.length();) {
                size_t j = i;
                while(j<sentence.length() && sentence[j]!=' ') j++;
                string word = sentence.substr(i,j-i);
                result += trie.findPrefix(word);
                if(j!=sentence.length()) result += " ";
                i = j+1;
            }
            return result;
        }
    private:
        class Trie {
        public:
            Trie(size_t size): sz(size), root(new TrieNode(sz)) {}
            
            ~Trie() {delete root;}
            
            void insert(const string& word) {
                insert(word,0,root);
            }
            
            string findPrefix(const string& word) {
                size_t len = findPrefix(word,0,root);
                return len==-1? word:word.substr(0,len);
            }
            
        private:
            
            struct TrieNode {
                TrieNode(size_t sz):child(vector<TrieNode*>(sz,NULL)), isLeaf(false) {}  
                ~TrieNode() {
                    for(TrieNode* node:child) delete node;
                }
                vector<TrieNode*> child;
                bool isLeaf;
            };
            
            size_t sz;
            TrieNode* root;
            
            void insert(const string& word, size_t i, TrieNode* cur) {
                if(i==word.length()) return;
                size_t j = word[i] - 'a';
                if(!cur->child[j]) 
                    cur->child[j] = new TrieNode(sz);
                if(i==word.length()-1) 
                    cur->child[j]->isLeaf = true;
                insert(word,i+1,cur->child[j]);
            }
            
            size_t findPrefix(const string& word, size_t i, TrieNode* cur) {
                if(i==word.length()) return -1;
                size_t j = word[i] - 'a';
                if(!cur->child[j]) return -1;
                if(cur->child[j]->isLeaf) return i+1;
                return findPrefix(word,i+1,cur->child[j]);
            }
            
        };
    };
    

  • 1

    Sharing my trie solution 24ms (99%) @ 2017-08-04 20:10:47

    public class Solution {
        public static class Node {
            String word = null;
            Node[] ar = new Node[26];
        }
    
        public String replaceWords(List<String> dict, String sentence) {
            if (dict.size() == 0 || sentence.length() == 0)
                return "";
            StringBuilder sb = new StringBuilder();
            String[] words = sentence.split(" ");
            Node root = new Node();
            for (String s : dict) {
                insert(root, s.toCharArray(), 0);
            }
            for (int i = 0; i < words.length; i++) {
                sb.append(get(root, words[i].toCharArray(), 0));
                if (i < words.length - 1)
                    sb.append(" ");
            }
            return sb.toString();
        }
    
        public void insert(Node node, char[] chs, int index) {
            if (node.word != null)
                return;
            if (index == chs.length) {
                node.word = String.valueOf(chs);
                return;
            }
            char ch = chs[index];
            if (node.ar[ch - 'a'] == null) {
                node.ar[ch - 'a'] = new Node();
            }
            insert(node.ar[ch - 'a'], chs, index + 1);
        }
    
        public String get(Node node, char[] chs, int index) {
            if (node.word != null)
                return node.word;
            if (index >= chs.length)
                return String.valueOf(chs);
            char ch = chs[index];
            if (node.ar[ch - 'a'] == null)
                return String.valueOf(chs);
            return get(node.ar[ch - 'a'], chs, index + 1);
        }
    }
    

    The explanation is available.


Log in to reply
 

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