面试金典题3

URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。

示例 1：

输入："Mr John Smith    ", 13
输出："Mr%20John%20Smith"

示例 2：

输入："               ", 5
输出："%20%20%20%20%20"

提示：

• 字符串长度在 [0, 500000] 范围内。

最直接的一种方法是重新定义一个字符串来存储要返回的字符，如果原字符串有空格，则返回%20，若不是空格，则返回原字符

leetcode代码

class Solution {
public:string replaceSpaces(string S, int length) {string str;for(int i=0;i<length;i++){if(S[i]==' '){str+="%20";}else{str+=S[i];}}return str;}
};

class Solution {
public:string replaceSpaces(string S, int length) {int i=length-1;int j=S.size()-1;while(i>=0){if(S[i]==' '){S[j--]='0';S[j--]='2';S[j--]='%';}else{S[j--]=S[i];}i--;}//注意是j+1,因为最后对下标0的位置赋值之后还要做一次j--return S.substr(j+1);}
};

第二种方法其实也比较容易想到，比起第一种办法不浪费空间，采用双指针的方式，对同一个字符串进行操作。

有大佬知道为什么用replace方法会超时吗？跪谢！！！！