93 单词替换（648）

作者: Turbo时间限制: 1S章节: 其它

晚于: 2020-09-09 12:00:00后提交分数乘系数50%

问题描述 :

在英语中，我们有一个叫做 词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

你需要输出替换之后的句子。

示例 1：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"

输出："the cat was rat by the bat"

示例 2：

输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"

输出："a a b c"

示例 3：

输入：dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"

输出："a a a a a a a a bbb baba a"

示例 4：

输入：dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"

输出："the cat was rat by the bat"

示例 5：

输入：dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"

输出："it is ab that this solution is ac"

可使用以下main函数：

int main()

{

    int n;

    vector<string> dict;

    string sentence,word;

    cin>>n;

    for(int i=0; i<n; i++)

    {

        cin>>word;

        dict.push_back(word);

    }

    cin.get();

    getline(cin, sentence);

    string res=Solution().replaceWords(dict, sentence);

    cout<<res;

}

输入说明 :

首先输入字典的单词数n，

然后输入n个单词，每个单词均由小写字母组成，长度在1到100之间。

最后输入一个字符串sentence，

1 <= sentence.length <= 10^6

sentence 仅由小写字母和空格组成。

sentence 中单词的总量在范围 [1, 1000] 内。

sentence 中每个单词的长度在范围 [1, 1000] 内。

sentence 中单词之间由一个空格隔开。

sentence 没有前导或尾随空格。

输出说明 :

输出一个字符串

输入范例 :

3 cat bat rat the cattle was rattled by the battery

输出范例 :

the cat was rat by the bat

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution 
{
public:
    string replaceWords(vector<string>& dict, string& sentence) 
    {
        unordered_map<string,int> map;
        for(auto i:dict)
            map[i]=1;
        string res="";
        for(int i=0;i<sentence.size();)
        {
            int j=i,flag=0;
            string temp="";
            while(j<sentence.size()&&sentence[j]!=' ')
            {
                if(!flag)
                    temp+=sentence[j];
                if(map[temp])
                    flag=1;
                j++;
            }
            res+=temp;
            if(j<sentence.size())
                res+=" ";
            i=j+1;
        }
        return res;
    }
};

int main()
{
    int n;
    vector<string> dict;
    string sentence,word;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>word;
        dict.push_back(word);
    }
    cin.get();
    getline(cin, sentence);
    string res=Solution().replaceWords(dict, sentence);
    cout<<res;
}