Replace Words

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".

Given a dictionary consisting of many roots and a sentence consisting of words spearted by spaces. You need to replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root with the shortest length.

Return the sentence after the replacement.

 

Example 1:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"

Example 3:

Input: dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
Output: "a a a a a a a a bbb baba a"

Example 4:

Input: dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Example 5:

Input: dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
Output: "it is ab that this solution is ac"

 

Constraints:


Solution:

class Solution {
    static class TrieNode {
        char c;
        boolean isWord;
        TrieNode[] children;
        
        public TrieNode(char c) {
            this.c = c;
            this.isWord = false;
            this.children = new TrieNode[26];
        }
    }
    
    static class Trie {
        TrieNode[] roots;
        
        public Trie() {
            roots = new TrieNode[26];
        }
        
        public void addWord(String s) {
            TrieNode[] nodes = roots;
            for (int i = 0; i < s.length(); i ++) {
                char c = s.charAt(i);
                TrieNode curr = nodes[c - 'a'];
                if (curr == null) {
                    curr = new TrieNode(c);
                }
                if (i == s.length() - 1) {
                    curr.isWord = true;
                }
                nodes[c - 'a'] = curr;
                nodes = curr.children;
            }
        }
        
        public String find(String s) {
            TrieNode[] nodes = roots;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i ++) {
                char c = s.charAt(i);
                TrieNode curr = nodes[c - 'a'];
                if (curr == null) {
                    // System.out.println(c + ", " + s);
                    return s;
                }
                sb.append(c);
                if (curr.isWord) {
                    return sb.toString();
                }
                nodes = curr.children;
            }
            return s;
        }
    }
    
    public String replaceWords(List<String> dictionary, String sentence) {
        Trie trie = new Trie();
        for (String s : dictionary) {
            trie.addWord(s);
        }
        String[] arr = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String s : arr) {
            String root = trie.find(s);
            sb.append(root + " ");
        }
        sb.setLength(sb.length() - 1);
        return sb.toString();
    }
}