Replace Words

• Lintcode : 1110 / Leetcode : 648
• Level : Medium

Problem

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
Example 1:

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

Input: 
dict = ["go", "begin", "make","end"]
sentence = "a good beginning makes a good ending"
Output: 
"a go begin make a go end"
Notice
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

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(string number of dict * split words)
space: O(string number of dict)

Answer

class Solution {
public:
    /**
     * @param dict: List[str]
     * @param sentence: a string
     * @return: return a string
     */
    string replaceWords(vector<string> &dict, string &sentence) {
        if (sentence.length() == 0 || dict.size() == 0) return sentence;
        vector<string> words;
        string temp = sentence;
        int index = 1;

        while (index != -1) {
            index = temp.find(" ");
            if (index == -1) break;
            string str = temp.substr(0, index);
            words.push_back(str);
            temp = temp.substr(index + 1);
        }

        if (temp.size() != 0) words.push_back(temp);
        set<string> set;

        for (auto s : dict) set.insert(s);

        for (auto &i : words) {
            for (auto it = set.begin(); it != set.end(); it++) {
                if (i.find(*it) == 0) i = *it; 
            }
        }
        string ans;
        for (auto s : words) {
            ans += " ";
            ans += s;
        }
        return ans.substr(1);
    }
};

tags: string

​