替换空格

描述

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ti-huan-kong-ge-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

如果想把这道题目做到极致，就不要只用额外的辅助空间了！

首先扩充数组到每个空格替换成”%20”之后的大小。

然后从后向前替换空格，也就是双指针法，过程如下：

i指向新长度的末尾，j指向旧长度的末尾。

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;
    }
};