当前位置：首页 > web >正文

C++代码随想录刷题知识分享-----替换数字字符 —— 字符串空间扩展与逆向填充技巧

web 2025/6/20 7:35:48

一、题目描述

给定一个只包含小写英文字母和数字的字符串 s，请将其中的数字字符（0–9）替换为字符串 "number"，其他字母字符保持不变。

不允许使用额外的临时字符串；
要求就地替换并尽量节省空间与时间复杂度；
数据范围：1 <= s.length < 10000

✍️ 输入输出示例

示例 1：

输入：a1b2c3
输出：anumberbnumbercnumber

示例 2：

输入：a5b
输出：anumberb

二、解题思路分析

📌 问题本质：

我们需要将所有的数字字符（长度为 1）替换成长度为 6 的字符串 "number"，这意味着：每个数字字符带来 +5 的长度扩展。

由于不能使用额外字符串，我们只能扩展原字符串空间，然后从后往前填充，防止数据覆盖。

🧱 三步解决方案：

统计数字字符个数 count
- 每个数字替换后多出 5 个字符。
- 总扩展长度为 count * 5
字符串扩容
- 使用 s.resize(new_length) 扩展字符串空间。
双指针倒序替换
- left 指针指向原始尾部，right 指向扩展后的尾部；
- 从尾部开始向前扫描字符，如果是字母就复制过去；
- 如果是数字，则在 right 位置插入 "number" 字符串。

三、完整 C++ 实现代码

#include <iostream>
using namespace std;int main() {string s;cin >> s;int count = 0;// 1. 统计数字个数for (int i = 0; i < s.size(); i++) {if (s[i] >= '0' && s[i] <= '9') {count++;}}int originalLength = s.size();int newLength = originalLength + count * 5;  // 每个数字字符扩展5个字符s.resize(newLength); // 扩展字符串空间int left = originalLength - 1;  // 指向原末尾int right = newLength - 1;      // 指向新末尾// 2. 倒序双指针替换while (left >= 0) {if (s[left] >= '0' && s[left] <= '9') {// 用 "number" 替换数字字符s[right--] = 'r';s[right--] = 'e';s[right--] = 'b';s[right--] = 'm';s[right--] = 'u';s[right--] = 'n';} else {s[right--] = s[left];}left--;}// 3. 输出最终结果cout << s << endl;return 0;
}

四、核心算法亮点总结

✨ 1. 逆序双指针技巧

从尾部向前填充是许多原地修改类字符串题的关键。
避免使用额外空间，尤其适用于大字符串处理。

✨ 2. 字符类型判断

if (s[i] >= '0' && s[i] <= '9')

使用 ASCII 码判断数字字符；
或者可替换为标准函数 isdigit(s[i])（包含 <cctype>）。

✨ 3. 空间控制合理

只扩展了最小必要空间；
无需使用辅助字符串或数组。

五、工程扩展与应用场景

这种替换逻辑常用于：

URL 编码：如将空格替换为 %20。
输入预处理：如将数字屏蔽或脱敏。
日志归档系统：替换字符进行清洗。
自然语言处理：标记特定类型词元（token）等。

💡 若将 “number” 改为其他字符串，如 “digit”，或替换字母为其他字符串，也只需调整插入逻辑即可。

六、算法复杂度分析

项目	分析
时间复杂度	$O(n)$（扫描一次 + 倒序替换一次）
空间复杂度	$O(1)$（就地操作，无辅助空间）
扩展字符串空间	$O(n + count * 5)$

适用于大输入场景，如长度达万级字符的字符串处理任务。