替换空格 题解

1
2
3
4
5
6
请实现一个函数，把字符串中的每个空格替换成"%20"。
你可以假定输入字符串的长度最大是 1000。
注意输出字符串的长度可能大于 1000。
样例
输入："We are happy."
输出："We%20are%20happy."
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//--------------------线性遍历---------------------
string replaceSpaces(string &str) {
    string s;
    for(auto c : str){
        if(c == ' ') s += "%20";
        else s += c;
    }
    return s;     
}
//--------------------双指针法----------------------
//倒序循环的原因：如果正序，因为j增加的速度比i快，j会将i还未遍历的部分给覆盖。
//倒序遍历就可以避免这个问题
string replaceSpaces(string &str) {
        int len;
        //先求出替换后的字符串的长度，为后面倒序遍历做准备
        for(auto c : str){
            if(c == ' ') len += 3;
            else len += 1;
        }
        
        int i = str.size() - 1, j = len - 1;//倒序遍历
        
        str.resize(len);//resize替换后的字符串长度
        
        while(i >= 0){
            if(str[i] == ' ') {
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
            }
            else str[j--] = str[i];
            i--;
        }
        return str;
    }