[leetcode]剑指 Offer 05. 替换空格

[leetcode]剑指 Offer 05. 替换空格

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

思路：
由于C++的string类型是可变的，于是可以实现时间复杂度O(n)，空间复杂度O(1)的算法。

遍历字符串，统计空格个数spaceCount，则新字符串的长度应为原字符串的长度+2*spaceCount。
resize空间之后，从后向前双指针替换字符串。即遇到不是空格，复制字符，继续向前，遇到空格开始将前面三个字符替换为"%20"。直到两指针相遇。

AC代码：（C++）

class Solution {
   public:
    string replaceSpace(string s) {
        int spaceCount = 0, len = s.size();
        for (char c : s) {
            if (c == ' ') {
                spaceCount++;
            }
        }
        s.resize(len + spaceCount * 2);
        int j = s.size() - 1, i = len - 1;
        while (i < j) {
            if (s[i] != ' ') {
                s[j] = s[i];
            } else {
                s[j - 2] = '%';
                s[j - 1] = '2';
                s[j] = '0';
                j -= 2;
            }
            i--;
            j--;
        }
        return s;
    }
};