代码随想录刷题-字符串-剑指 Offer 05. 替换空格

剑指 Offer 05. 替换空格

本节对应代码随想录中：代码随想录，讲解视频：暂无

习题

题目链接：剑指 Offer 05. 替换空格 - 力扣（LeetCode）

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."

新建字符串保存结果

题目并不难，不过要写出好的解法并不简单，首先说下常规思维。

新建一个字符串 res 用来保存结果，遍历一遍数组，当遇到空格时，让 res+=%20，否则让 res+原始的字符

class Solution {public:string replaceSpace(string s) {string res = "";for (int i = 0; i < s.length(); i++) {if (s[i] == ' ') {res += "%20";} else {res += s[i];}}return res;}
};

• 时间复杂度：O($n$)。其中n是输入字符串s的长度。 因为代码中有一个循环，它遍历了整个输入字符串一次，所以时间复杂度与n成正比
• 空间复杂度：O($n$)。最坏的情况下，输出字符串 res 的长度将是输入字符串 s 的三倍，即当 s 中每个字符都是空格时，需要3n 的额外空间来存储结果

replace 函数

C++的 replace 函数并没有 java 等语言的用法，直接 return s.replace(" ","%20"); 就可以

C++中 replace 函数有三个参数：替换的起始位置、替换的字符数量和替换区域的新字符串。那么我们只需遍历一遍字符串，当遇到空格时，将当前位置替换成 %20 即可

class Solution {public:string replaceSpace(string s) {for (int i = 0; i < s.length(); i++) {if (s[i] == ' ') {s.replace(i, 1, "%20");}}return s;}
};

• 时间复杂度：O(n2n^2n2)。每次调用replace()函数时都需要将整个字符串后面的字符向后移动，以便为放置新字符腾出空间。因此，在最坏的情况下，即当输入字符串中的每个字符都是空格时，使用replace()函数会将第i个字符替换成"%20"时，必须将i之后的所有字符都向后移动，这需要O(n)的时间复杂度。由于需要执行n次这样的操作，因此总时间复杂度为O(n^2)
• 空间复杂度：O($1$)。只使用了常量级别的额外空间。虽然在每次调用 replace() 函数时，字符串的长度都会增加，但最终返回的字符串仍然是原始字符串 s，因此不需要额外的空间来存储结果

双指针

这题比较推荐的就是双指针解法。首先将字符串扩充至替换后的大小，然后从后向前遍历，i 指向新长度的末尾，j 指向旧长度的末尾。当 s[i]!=' ' 时，直接将 s[i]的值赋给是 s[j]即可。当 s[i]==' ' 时，将 s[j]位置及其前面的两个位置填充为 %20，并将 j 指针-2以移到填充后的 %20 的 % 的位置，下一轮循环时，i 和 j 均向前移动到新的位置。结束条件是 j<i，当等于的时候说明两个指针相遇没必要再进行操作了。

很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作

class Solution {
public:string replaceSpace(string s) {int count = 0; // 统计空格的个数int sOldSize = s.size();for (int i = 0; i < s.size(); i++) {if (s[i] == ' ') {count++;}}// 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小s.resize(s.size() + count * 2);int sNewSize = s.size();// 从后先前将空格替换为"%20"for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {if (s[j] != ' ') {s[i] = s[j];} else {s[i] = '0';s[i - 1] = '2';s[i - 2] = '%';i -= 2;}}return s;}
};

• 时间复杂度：O($n$)。其中 n 是字符串 s 的长度。遍历字符串 s 两次，因此时间复杂度是 O(n)
• 空间复杂度：O($1$)。我们是在原字符串上进行操作，而不需要使用额外的空间