题目描述在英语中我们有一个叫做词根(root) 的概念可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为衍生词(derivative)。例如词根help跟随着继承词ful可以形成新的单词helpful。现在给定一个由许多词根组成的词典dictionary和一个用空格分隔单词形成的句子sentence。你需要将句子中的所有衍生词用词根替换掉。如果衍生词有许多可以形成它的词根则用最短的词根替换它。你需要输出替换之后的句子。示例 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题解class Mycompare { public: bool operator()(string s1,string s2) { return s1.size()s2.size(); } }; class Solution { public: string replaceWords(vectorstring dictionary, string sentence) { vectorstring strs; int start 0; int end0; for(;endsentence.size();end){ if(sentence[end] ){ string sub sentence.substr(start,end-start); start end1; strs.push_back(sub); } } string sub sentence.substr(start,end-start); strs.push_back(sub); sort(dictionary.begin(),dictionary.end(),Mycompare()); string res ; for(int i0;istrs.size();i){ bool flag false; for(int j0;jdictionary.size();j){ if(strs[i].find(dictionary[j])0){ res dictionary[j]; flag true; res ; break; } } if(!flag){ resstrs[i]; res ; } } return res.substr(0,res.size()-1); } };超出时间限制注意std::string::find(const string substr)返回的是size_t类型即std::string::size_type表示子串首次出现的索引位置。如果没找到返回的是std::string::npos一个特殊的size_t值通常是-1的无符号形式当前的代码时间复杂度是分割句子O(L)L 是句子长度排序词典O(M log M)M 是词典大小匹配过程O(N × M × K)其中N 单词数M 词典大小K 平均前缀比较长度find的开销⚠️瓶颈在双重循环 string::find—— 即使你按长度排序并break最坏情况下仍要遍历整个词典。最优解法使用 Trie前缀树Trie 可以将匹配过程从O(M·K)降到O(K)每个单词总时间复杂度降至 O(L total_chars_in_dictionary)。而且天然保证“最短前缀优先”—— 一旦在 Trie 中遇到一个标记为词根的节点立即返回无需排序class Solution { // 定义 Trie 节点结构 struct Trie { string word; // 如果该节点是一个词根的结尾则存储该词根否则为空 Trie* children[26] {}; // 指向子节点的指针数组对应 a 到 z }; public: string replaceWords(vectorstring dict, string sentence) { // 创建 Trie 根节点 Trie* root new Trie(); // 1️⃣ 将词典中的所有词根插入 Trie for (auto w : dict) { Trie* cur root; // 从根节点开始插入 for (char c : w) { int idx c - a; // 将字符转换为 0~25 的索引 // 如果当前字符对应的子节点不存在则创建新节点 if (!cur-children[idx]) { cur-children[idx] new Trie(); } // 移动到子节点 cur cur-children[idx]; } // 只有当该节点尚未存储词根时才保存当前词避免长词覆盖短词 // 注意由于我们不预先对 dict 排序这里“先插入的优先” // 但 LeetCode 测试用例中即使后插入更短的词也不会覆盖 // 所以更安全的做法是先对 dict 按长度排序或在查询时保证最短匹配。 // 不过本题中只要在查询时“首次命中就返回”就能保证最短前缀。 if (cur-word.empty()) { cur-word w; } } // 2️⃣ 分割句子并逐个处理单词 string res; // 最终结果字符串 string word; // 临时存储每个单词 istringstream iss(sentence); // 使用 stringstream 按空格分割句子 while (iss word) { // 依次读取每个单词 Trie* cur root; // 从 Trie 根节点开始查找 for (char c : word) { // 如果当前路径已断节点为空 或 子节点不存在跳出 if (!cur || !cur-children[c - a]) { break; } // 进入下一个字符对应的子节点 cur cur-children[c - a]; // ✅ 关键一旦发现当前路径构成一个词根word 非空立即替换 // 因为我们是从前往后遍历单词第一个匹配的词根一定是最短的 if (!cur-word.empty()) { word cur-word; // 替换为词根 break; // 停止继续匹配更长的前缀 } } // 将处理后的单词加入结果注意处理空格 if (!res.empty()) { res ; } res word; } return res; } };补充使用stringstream适合空格、制表符等空白字符分割#include iostream #include sstream #include string #include vector int main() { std::string input apple\tbanana cherry\n date \t\telderberry; std::stringstream ss(input); std::string word; std::vectorstd::string tokens; // 使用 操作符从 stringstream 中逐个读取非空白 token while (ss word) { tokens.push_back(word); } // 输出结果 for (const auto w : tokens) { std::cout w \n; } return 0; }apple banana cherry date elderberrystd::stringstream的operator默认以任意空白字符包括空格、\t、\n、\r、\f、\v作为分隔符。它会自动跳过多余的空白包括开头、结尾和中间连续的空白非常适合解析由空白分隔的“单词”或“字段”。