剑指 Offer 05. 替换空格

难度简单455

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

(资料图片仅供参考)

示例 1：

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

限制：

0 <= s 的长度 <= 10000

通过次数635,989提交次数843,510

第一种对法：

class Solution {

public:

string replaceSpace(string s) {

string ans;

for(auto a:s){

if(a==' '){

ans+="%20";

}else{

ans+=a;

}

}

return ans;

}

};

思路：

时间复杂度：O(n) 空间复杂度: O(n)

开一个新的字符串来存答案，当检测到是空格时将%20存到答案串中，不是空格时将字符存入到答案串中

第二种对法：

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.resize(s.size()+count*2);

int sNewSize = s.size();

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)，空间复杂度O(1)

先数清楚字符串中有多少个空格，将原来的字符串resize成可以装下答案字符串的长度

让快指针指向倒数原串的末尾，让慢指针指向新的字符串长度的末尾

快慢指针不断往后移动

当快指针指向的是字符时，就让慢指针将指向的位置改成字符

当快指针指向的是空格时，就让慢指针将指向的位置与后两个位置分别改成‘0’ ‘2’ ‘%’，然后慢指针-2迭代