※ 引述 《Rushia (早瀬ユウカの体操服)》 之铭言：
: 　
: https://leetcode.com/problems/replace-words/description
: 648. Replace Words
: 给你一个字串行表dictionary和一个字串sentence，sentence里面有很多单字，这些单字
: 被空白分割，有些单字是从其他单字的字首延伸的例如：helpful = help+ful 若
: sentence里面的单字字首存在于dictionary我们可以把原单字替换成较短的字首，若
: 存在多个字首则取最短，求出替换完的句子长什么样子。
: 　
: Example 1:
: Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled
: by the battery"
: Output: "the cat was rat by the bat"
: 　
: 思路:
: 1.前面忘了中间忘了凭印象手刻一个字典树，先把所有字根加入字典树。
: 2.接下来把sentence依照空白切成单字，如果这个单字在字典树里面就加入第一个找到的
: 字根，找不到就返回原单字。
: 3.把结果集串起来用空白分割。
: 　
思路 :
c++没有内建字典树
我懒得刻
所以用unordered set 里面放 string 代替
然后每次进来的字母都去找set里面有没有
有的话就加进res 并且跳到下一个空格
就好了
好想姆咪
class Solution {
public:
string replaceWords(vector<string>& dictionary, string sentence)
{
int len = dictionary.size();
unordered_set<string> paper;
for(int i = 0 ; i < len ; i ++)
{
paper.insert(dictionary[i]);
}
int slen = sentence.size();
string res ;
for(int i = 0 ; i < slen ; i ++)
{
string k ;
while(i < slen && sentence[i] != ' ')
{
k += sentence[i];
i++;
if(paper.find(k) != paper.end())
{
while(i < slen && sentence[i] != ' ')
{
i++;
}
}
}
res += k;
res += " ";
}
res.pop_back();
return res;
}
};

大师 教我

你好厉害