648. 单词替换

题目描述

在英语中，我们有一个叫做词根(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(vector<string>& dictionary, string sentence) { vector<string> strs; int start = 0; int end=0; for(;end<sentence.size();end++){ if(sentence[end]==' '){ string sub = sentence.substr(start,end-start); start = end+1; 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 i=0;i<strs.size();i++){ bool flag = false; for(int j=0;j<dictionary.size();j++){ if(strs[i].find(dictionary[j])==0){ res +=dictionary[j]; flag = true; res+=" "; break; } } if(!flag){ res+=strs[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(vector<string>& 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::vector<std::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' 'elderberry'

• std::stringstream的operator>>默认以任意空白字符（包括空格、\t、\n、\r、\f、\v）作为分隔符。
• 它会自动跳过多余的空白（包括开头、结尾和中间连续的空白），非常适合解析由空白分隔的“单词”或“字段”。