648. Replace Words

648. Replace Words

Question

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, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

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

Note:

• The input will only have lower-case letters.
• 1 <= dict words number <= 1000
• 1 <= sentence words number <= 1000
• 1 <= root length <= 100
• 1 <= sentence words length <= 1000

Thinking:

• Method 1:Trie Tree

class Solution {
    private static class TrieTree{
        public static class Node{
            boolean isLeaf;
            Node[] childs;
            public Node(){
                this.childs = new Node[26];
            }
        }
        private Node root;
        public TrieTree(){
            this.root = new Node();
        }
        public void insert(String s){
            char[] arr = s.toCharArray();
            Node node = root;
            for(int i = 0; i < arr.length; i++){
                if(node.isLeaf) return;
                int c = arr[i] - 'a';
                if(node.childs[c] == null){
                    node.childs[c] = new Node();
                }
                node = node.childs[c];
            }
            node.isLeaf = true;            
        }
        public String findClosest(String s){
            char[] arr = s.toCharArray();
            Node node = root;
            for(int i = 0; i < arr.length; i++){
                int c = arr[i] - 'a';
                if(node.childs[c] == null){
                    return s;   
                }else{
                    node = node.childs[c];
                    if(node.isLeaf){
                        return s.substring(0, i + 1);   
                    }
                }
            }
            return s;
        }
    }
    public String replaceWords(List<String> dict, String sentence) {
        if(sentence == null || sentence.length() == 0) return "";
        if(dict == null || dict.size() == 0) return sentence;
        TrieTree tree = new TrieTree();
        for(String s : dict){
            tree.insert(s);
        }
        StringBuilder sb = new StringBuilder();
        String[] tokens = sentence.split(" ");
        for(String token : tokens){
            sb.append(" " + tree.findClosest(token));
        }
        return sb.toString().substring(1);
    }
}