精品题解 🔥 《九章斩题录》 👈 猛戳订阅
JZ5 - 替换空格
📚 题目：请实现一个函数，将一个字符串 
中的每个空格替换成 " %20 " 。例如当字符串为 We Are Happy. 则经过替换之后的字符串为 We%20Are%20Happy 。
💭 示例：I/O
输入："We Are Happy" 返回："We%20Are%20Happy" 输入：" " 返回："%20"
✅ 模板：C语言
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ char* replaceSpace(char* s ) { // write code here }
✅ 模板：C++
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ string replaceSpace(string s) { // write code here } };
「 法一 」暴力美学
💡 思路：两次循环遍历整个数组，第一次循环寻找空格的位置，第二次循环将空格后的字符整体后移 2 个单位 (腾出空间给 %20)，然后再将 %20 插入即可。因为 ''%20'' 为 3 个字符，分别是 (%, 2, 0)，因为空格处用来放置 '%'，所以只需腾出 2 个空间给 '2' 和 '0' 即可。
循环次数为两次，因此时间复杂度为 ，空间复杂度为 。
💬 代码演示：C++
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ string replaceSpace(string s) { // 统计空格数 int i = 0; int count = 0; for (i = 0; i < s.size(); i++) { if (s[i] == ' ') { count++; } } // 重新开大小，大小为 旧字符串大小 + 空格数 x 2 // 这样就有足够的位置放 %20了 // 原字符串空格放%，新开的放 2 和 0 s.resize(s.size() + count * 2); i = 0; int j = 0; while (i < s.size()) { if (s[i] == ' ') { // 整体后移两个单位 for (j = s.size() - 1; j > i + 2; j--) { s[j] = s[j - 2]; } s[i] = '%'; s[i + 1] = '2'; s[i + 2] = '0'; } else { i++; } } return s; // 返回原字符串 } };
「 法二 」另开数组
💡 思路：我们直接重新开一个字符数组，依次读取原整个字符串的内容，读到空格就在后面加上 '‘%20'' 然后继续读。其主要思路如下：
① 创建一个新的字符型数组，用于存放替换空格后的字符串。
② 从头到尾遍历字符串 
，遍历到 \0 为止。
③ 对每个字符都进行判断，判断当前字符是否为空格，如果为空格就分别向后插入 %, 2, 0。
④ 如果当前字符不是空格，就将当前字符串的字符直接加到新数组中。
⑤ 最后记得在新数组末尾手动加上 \0，最后返回新数组即可，此时就实现了空格的替换。
这种方法需要创建新的空间，不修改源字符串，这种方法非常易于理解和实现，属于 "重新来过" 的思想。其时间复杂度为 ，空间复杂度为 。
💬 代码演示：C
char* replaceSpace(char* s ) { char arr[10000] = {0}; int i = 0; while (*s != '\0') { if (*s == ' ') { arr[i++] = '%'; arr[i++] = '2'; arr[i++] = '0'; } else { arr[i++] += *s; } s++; } arr[i] = '\0'; return arr; }
「 法三 」反向搜空格然后替换（利用 rfind + replace）
💡 思路：有现成的 replace 接口可以拿来替换，又有现成的 find 接口可以拿来查找空格。直接调接口来解决问题，岂不美哉？这里我们用 rfind 反向查找，从字符串 
的末尾向前查找空格，如果找到就调用 replace 把空格替换成 '%20' 即可。
💬 代码：C++
class Solution { public: string replaceSpace(string s) { int end = s.size() - 1; // 字符串s的最后一个元素的下标 while (string::npos != s.rfind(' ', end)) { int space = s.rfind(' ', end); // 倒着找空格，避免覆盖 s.replace(space, 1, "%20"); // 将字符串s中空格开始的1个字符替换为%20 end = space; // 下次从空格前一个位置开始查找 } return s; } };
先定义 end 用于记录最后一个字符的位置，然后倒着遍历字符串。这里的循环条件是判断 rfind 是否为 npos，因为当find 或 rfind 在字符串中找不到指定字符或子字符串时，它们会返回 string::npos。如果是 npos 那就说明没找到空格，说明查找完毕了，就结束循环。如果有空格，我们就记录空格的位置，然后调用 replace，把空格替换成 %20，然后更新我们的 end。每次循环都会判断是否存在空格，如果从右向左找一遍没有空格也就没有必要在进入循环，说明没有需要替换的，或者已经替换完了，这时直接 return s 即可。
⚡ 代码简化：
class Solution { public: string replaceSpace(string s) { int space, end = s.size() - 1; for (; (space = s.rfind(' ', end)) != string::npos; end = space) s.replace(space, 1, "%20"); return s; } };
「 整活 」不用C++了，Python 一行代码搞定
"人生苦短，我用 Python…… "
不用做了，用隔壁蟒蛇直接一行结束了。
return s.replace(' ', "%20")
📌 [ 笔者 ] 王亦优 📃 [ 更新 ] 2023.5.30 ❌ [ 勘误 ] /* 暂无 */ 📜 [ 声明 ] 由于作者水平有限，本文有错误和不准确之处在所难免， 本人也很想知道这些错误，恳望读者批评指正！
📜 参考资料 C++reference[EB/OL]. []. http://www.cplusplus.com/reference/. Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. . 百度百科[EB/OL]. []. https://baike.baidu.com/. 牛客网. 剑指offer 题解 [EB/OL]. []. https://www.nowcoder.com/exam/oj/ta?tpId=1kon |
