题目

题解

1. 双指针法

先统计空格个数，然后扩容，然后用双指针挨个从前往后复制数据，不需要额外空间

  • 时间复杂度$O(n)$,遍历两遍
  • 空间复杂度$O(1)$
class Solution {//两个方法。1. 双指针法
public:
    string replaceSpace(string s) {
        int n = s.size();//原字符串长度
        int space_num = 0;//总空格数
        for(int i=0; i<n; ++i){
            if(s[i] == ' ')space_num++;
        }//统计空格数
        int p1 = n-1, p2 = n+space_num*2-1;//双指针，指向原字符串和新字符串末尾
        s.append(space_num*2,'#');//字符串扩容
        while(p1>=0 && p2>p1){//当p1没到头，或者p2没追上p1（也可以p1，p2都没到头），继续向前遍历
            if(s[p1] == ' '){//遇到空格，p2加上%20
                s[p2--]='0';
                s[p2--]='2';
                s[p2--]='%';
            }else{//没遇到空格，p2=p1
                s[p2--]=s[p1];
            }
            p1--;//注意p1向前移动
        }
        return s;
    }
};

2. 新string法

创建一个新string，从前往后遍历，遇到’ ‘就添加”%@20”，其他情况复制原char

  • 时间复杂度$O(n)$,遍历一遍
  • 空间复杂度$O(n)$
class Solution {//两个方法。2.新数组法
public:
    string replaceSpace(string s) {
        string res;
        for(int i=0; i<s.size(); ++i){
            if(s[i]==' ')res.append("%20");
            else res.push_back(s[i]);
        }
        return res;
    }
};