算法day_5 字符串处理专题

碎碎念

这是我在2024年12月21日的算法训练，加油！
  标题一：不常见单词查找

884. 两句话中的不常见单词
标题描述

给定两个句子 s1 和 s2，找出仅在此中一个句子中出现一次的单词。也就是说，这些单词在两个句子中只出现过一次，并且只出如今此中一个句子中。
示例

示例 1:

1. 输入: s1 = "this apple is sweet", s2 = "this apple is sour"
2. 输出: ["sweet","sour"]

复制代码

示例 2:

1. 输入: s1 = "apple apple", s2 = "banana"
2. 输出: ["banana"]

复制代码

解题思绪

• 字符串分割
  
  
  
  • 使用 C++ 的 istringstream 进行字符串分割，根据 C++ Reference 文档，这是处理空格分隔字符串的标准方法。
    
  • istringstream 会自动跳过空格，逐个读取单词。
    
  • 通过将两个句子分开处理，可以准确统计每个单词的总出现次数。
    
  
  
• 词频统计
  
  
  
  • 使用 unordered_map 记录每个单词的出现次数。
    
  • 遍历两个句子中的所有单词，并在哈希表中更新对应单词的计数。
    
  • 时间复杂度为 O(n)，此中 n 为总单词数。
    
  • 空间复杂度为 O(m)，此中 m 为不重复单词数。
    
  
  
• 结果筛选
  
  
  
  • 遍历哈希表，筛选出出现次数为 1 的单词，这些单词即为仅在一个句子中出现过的单词。
    
  
  

完备代码实现

1. #include <vector>
2. #include <string>
3. #include <unordered_map>
4. #include <sstream>
6. using namespace std;
8. class Solution {
9. public:
10.      vector<string> uncommonFromSentences(string s1, string s2) {
11.           unordered_map<string, int> wordsCount; // 哈希表用于记录单词频率
12.           string word;
13.           vector<string> result;
15.           // Lambda 函数用于处理字符串分割和词频统计
16.           auto helper = [&](const string& s) {
17.                istringstream iss(s);
18.                while (iss >> word) {
19.                     wordsCount[word]++;
20.                }
21.           };
23.           helper(s1); // 处理第一个句子
24.           helper(s2); // 处理第二个句子
26.           // 筛选出只出现一次的单词
27.           for (const auto& [key, value] : wordsCount) {
28.                if (value == 1) {
29.                     result.emplace_back(key);
30.                }
31.           }
33.           return result;
34.      }
35. };

复制代码

代码剖析

• unordered_map<string, int> wordsCount: 用于存储每个单词及其出现次数。
  
• helper Lambda 函数: 负责将输入的句子进行分割，并更新哈希表中的单词计数。
  
• 遍历哈希表: 通过遍历哈希表中的键值对，筛选出出现次数为 1 的单词，并将其添加到结果向量中。
  

时间复杂度分析

• 字符串分割: 每个句子都必要 O(n) 的时间进行分割。
  
• 词频统计: 由于使用了哈希表，插入和查找操作的匀称时间复杂度为 O(1)，总的词频统计时间复杂度为 O(n)。
  
• 结果筛选: 遍历哈希表，时间复杂度为 O(m)。
  

总体时间复杂度为 O(n)，此中 n 是两个句子中单词的总数。
标题二：字符串压缩

口试题 01.06. 字符串压缩
标题描述

实现一个方法，将一连重复的字符进行压缩。对于每一组一连重复的字符，替换成字符后跟其出现的次数。假如压缩后的字符串没有变短，则返回原始字符串。
示例

示例 1:

1. 输入："aabcccccaaa"
2. 输出："a2b1c5a3"

复制代码

示例 2:

1. 输入："abc"
2. 输出："abc"

复制代码

解题思绪

使用双指针技巧解决该题目：

• 指针设计
  
  
  
  • i 指针：标志当前处理字符的起始位置。
    
  • j 指针：向后搜索相同字符的结束位置。
    
  • 区间 [i, j) 表示一连相同字符段。
    
  
  
• 压缩规则
  
  
  
  • 记录每段相同字符的首字符和出现次数。
    
  • 当压缩后字符串更短时返回压缩后的字符串，否则返回原字符串。
    
  • 时间复杂度为 O(n)，此中 n 是字符串的长度。
    
  • 空间复杂度为 O(n)，用于存储压缩后的字符串。
    
  
  
• 优化点
  
  
  
  • 预先计算压缩后的字符串长度，可以避免在不必要的环境下进行字符串拼接。
    
  • 使用 ostringstream 或者直接构造字符串以提升效率。
    
  
  

完备实现

1. #include <string>
3. using namespace std;
5. class Solution {
6. public:
7.      string compressString(string S) {
8.           int i = 0, j = 0;
9.           string result;
11.           while (i < S.size()) {
12.                // 移动 j 指针，找到当前字符段的结束位置
13.                while (j < S.size() && S[i] == S[j]) {
14.                     j++;
15.                }
16.                // 记录当前字符及其出现次数
17.                result += S[i];
18.                result += to_string(j - i);
19.                i = j; // 更新 i 指针，开始处理下一个字符段
20.           }
22.           // 比较压缩后的字符串长度与原字符串的长度
23.           return result.size() < S.size() ? result : S;
24.      }
25. };

复制代码

代码剖析

• 指针 i 和 j: 用于标志当前正在处理的字符段的起始和结束位置。
  
• 字符串拼接: 将当前字符和其出现次数拼接到结果字符串中。
  
• 条件判断: 最后比较压缩后的字符串长度与原字符串长度，决定返回哪一个。
  

时间复杂度分析

• 主循环: 每个字符最多被遍历两次（一次由 i 指针，一次由 j 指针），时间复杂度为 O(n)。
  
• 字符串拼接: 在最坏环境下，每个字符都必要被拼接到结果字符串中，依然保持 O(n) 的时间复杂度。
  

总体时间复杂度为 O(n)，空间复杂度为 O(n)。
进一步优化

• 假如必要进步性能，可以思量预分配充足的空间给 result 字符串，避免多次内存分配。
  
• 在处理大量重复字符时，可以提前返回结果，减少不必要的计算。
  

总结

本日的两题也优劣常简朴的两题，主要观察了字符串处理的根本技巧。加油喔！
附加资源

• C++ istringstream 使用指南
  
• LeetCode 884. 两句话中的不常见单词 题解
  
• LeetCode 口试题 01.06. 字符串压缩 解题思绪
  
• 双指针算法详解
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。