题目描述

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

你可以假定输入字符串的长度最大是1000。
注意输出字符串的长度可能大于1000。

样例

输入："We are happy."

输出："We%20are%20happy."

思路

这道题我的实现是用另外的内存来存放结果，当然可以不用额外内存，思路差不多。
主要的思路是从后往前走（也可以从前往后走，但这样的时间复杂度较高，因为你需要在每次替换空格的时候将字符串中空格后面的字符都往后移动，最差情况下时间复杂度为$O(n^2))$。从后往前的好处是时间复杂度为$O(n)$，因为你可以将空格替换成%20而不影响前面的字符，所以不需要多余的字符移动。

代码

class Solution {
public:
    string replaceSpaces(string &str) {
        auto len = str.size();
        string ans, space("%20");
        if(len == 0) return ans;

        for( int i = len - 1; i >= 0 ; --i) {
            string tmp(str.substr(i, 1));
            if(str[i] == ' ') ans = space + ans;
            else ans = tmp + ans;
        }
        return ans;
    }
};