C++题解 | #替换空格#

本题要求替换空格为'%20'（空格可能会在格式不兼容时，成为乱码）,即将一个字符替换为一个字符串。若按正常从前按往后替换，则为避免覆盖空格其后字符，需要将其后字符后移两位，则会直接导致整个时间复杂度达到O(n^2)。况且在转移过程中，极有可能导致同一个子字符串的多次后移。
故而，此处采用从后往前替换的方法。当然，此方法前提是s要留有足够的空间。这个过程直接在s内部进行，可以减小空间复杂度（不必额外申请一个空字符串）。申请两个指针P1, P2，分别指向当前字符串尾部和替换完成后字符串尾部。若不是空格，则直接将s[P1]赋给s[P2]，而后P1--, P2--，若遇到空格,则P1--，s[P2]从后往前依次赋值为'0','2','%',即P2-3。依此类推，直到原来的s中所有的字符都遍历完成。
特别要注意的是，s虽有足够的容量放置替换完成后的字符串，但在替换过程中，s的size不会发生改变，即s被替换后，多于原来字符串s长度的字符，都无法被显示。故而，此处采用了提前给s追加一定长度字符，以便于替换后的字符串所有的字符都可以显示出。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        // write code here
        int n = s.length(), num = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == ' ') 
                num++;
        }
        int P1 = n - 1, P2 = n + num * 2 - 1;
        s.append(num * 2, 'a'); //增加s长度，使替换后的字符串全部都可以显示
        while(P1 >= 0 && P2 >= P1) {
            if (s[P1] == ' ') {
                P1--;
                s[P2--] = '0';
                s[P2--] = '2';
                s[P2--] = '%';
            }
            else {
                s[P2--] = s[P1--];
            }
        }
        return s;
    }
};