648. Replace Words.md

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);
    }
}

C++ version

class Solution {
public:
    string replaceWords(vector<string>& dict, string sentence) {
        root_.reset(new Node());
        string res = "", temp = "";
        for(const string & pattern: dict){
            insert(pattern);
        }
        istringstream is(sentence);
        while(is >> temp){
            if(!res.empty()) res += " ";
            res += findClosest(temp);
        }
        return res;
    }
private:
    struct Node{
        vector<Node*> childs;
        bool isLeaf;
        Node(): isLeaf(false), childs(26, nullptr){};
        ~Node(){
            for(auto node: childs){
                delete node;
            }
        }
    };
    std::unique_ptr<Node> root_;
    void insert(const string & word){
        Node* temp = root_.get();
        for(const char & c: word){
            if(!temp->childs[c - 'a']){
                temp->childs[c - 'a'] = new Node();
            }
            temp = temp->childs[c - 'a'];
        }
        temp->isLeaf = true;
    }
    string findClosest(const string & word){
        Node* temp = root_.get(); 
        string cur = "";
        for(const char c: word){
            cur += c;
            if(temp->childs[c - 'a']){
                if(temp->childs[c - 'a']->isLeaf)
                    return cur;
                else temp = temp->childs[c - 'a'];
            }else return word;
        }
        return word;
    }
};