(线性扫描) O(n)

class Solution {
public:
    string replaceSpaces(string &str) {
        string res;
        for (auto x : str)
            if (x == ' ') res += "%20";
            else res += x;
        return res;
    }
};

(双指针扫描) O(n)

class Solution {
public:
    string replaceSpaces(string &str) {
        int len = 0;
        for (auto c : str)
            if (c == ' ') len += 3;
            else len ++ ;

        int i = str.size() - 1, j = len - 1;
        str.resize(len);
        while (i >= 0)
        {
            if (str[i] == ' ')
            {
                str[j -- ] = '0';
                str[j -- ] = '2';
                str[j -- ] = '%';
            }
            else str[j -- ] = str[i];
            i -- ;
        }
        return str;
    }
};