648. 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, 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

解题思路：

从题目中可以看出限定条件：

　　词根长度最长为100，所有的输入均为小写，所以不存在大小写转换的问题。

需要考虑corner cases：

　　1.dictionary是否为空？

　　2.sentences是否为空字符串？

首先想到的是：

　　将所有词根加入hash表中，这样的存取是O(1)时间。

　　对于每个单词每个长度进行检测，是否有相应词根存在。

对于检查我们可以进行剪枝：

　　1. 因为我们只保存词根最短的单词，所以当我们寻找到的时候就不再检查后面可能出现的词根。

　　2.可以根据字典中存在的词根的最大长度和最小长度来缩小搜索的范围：

　　　　　　　　从最小长度开始取子字符串，最小长度需小于字符串长度，也需要小于等于最大长度

由于我们在构造最后的返回字符串时，每加入一个单词需要加入一个空格。

所以在句子的尾部我们有一个多余的空格，所以我们要pop_back()

代码：

class Solution {
public:
    string replaceWords(vector<string>& dict, string sentence) {
        unordered_set<string> s;
        int maxLen = 0, minLen = 100;
        for(string str : dict){
            maxLen = max(maxLen, (int)str.size());
            minLen = min(minLen, (int)str.size());
            s.insert(str);
        }
        
        string ret;
        string tmp;
        stringstream ss(sentence);
        while(getline(ss, tmp, ' ')){
            for(int i = minLen; i < tmp.size() && i <= maxLen; i++){
                string root = tmp.substr(0, i);
                if(s.count(root) != 0){
                    tmp = root;
                    break;
                }
            }
            ret += tmp + " ";
        }
        ret.pop_back();
        return ret;
    }
};