题目描述
URL化。编写一种方法，将字符串中的空格全部替换为%20。
假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。
（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）
示例 1：
输入："Mr John Smith ", 13
输出："Mr%20John%20Smith"
示例 2：
输入：" ", 5
输出："%20%20%20%20%20"
提示：
字符串长度在 [0, 500000] 范围内。
算法1
(逆序枚举) $O(n)$
看题意 题目似乎有个隐藏条件
不需要额外的空间 只在输入的字符串中进行计算
因为字符串的长度实际比输入的字符要大
那么我们可以倒序计算
两个指针分别指向字母和字符串的最末尾，
如果是其他字母则照样复制 两指针分别向前移动
如果是空格则在字符串末尾添加%20三个字符，向前移动三位，字母的指针则向前移动一位
C++ 代码
class Solution {
public:
string replaceSpaces(string S, int length) {
int fillIdx = S.size()-1;
int i = 0;
for ( i = length-1; i >= 0; i--) {
if (S[i] == ' ') {
S[fillIdx] = '0';
S[fillIdx - 1] = '2';
S[fillIdx - 2] = '%';
fillIdx -= 3;
}
else {
S[fillIdx] = S[i];
fillIdx--;
}
}
S = S.substr(fillIdx+1);
return S;
}
};
