剑指 Offer 05. 替换空格

难度简单455

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

 

示例 1：

输入：s = "We are happy."输出："We%20are%20happy."

 

限制：

0 <= s 的长度 <= 10000

通过次数635,989提交次数843,510

第一种对法：

class Solution {

public:

    string replaceSpace(string s) {

        string ans;

        for(auto a:s){

            if(a==' '){

                ans+="%20";

            }else{

                ans+=a;

            }

        }

        return ans;

    }

};

思路：

时间复杂度：O(n) 空间复杂度: O(n)

开一个新的字符串来存答案，当检测到是空格时将%20存到答案串中，不是空格时将字符存入到答案串中

第二种对法：

class Solution {

public:

    string replaceSpace(string s) {

        int count = 0;

        int sOldSize = s.size();

        for(int i=0;i<s.size();i++){

            if(s[i]==' '){

                count++;

            }

        }

        s.resize(s.size()+count*2);

        int sNewSize = s.size();

        for(int i = sNewSize - 1,j = sOldSize - 1;j < i;i--,j--){

            if(s[j]!=' '){

                s[i] = s[j];

            }else{

                s[i] = '0';

                s[i-1]='2';

                s[i-2]='%';

                i-=2;

            }

        }

        return s;

    }

};

思路：

双指针法，时间复杂度 O(n)，空间复杂度O(1)

先数清楚字符串中有多少个空格，将原来的字符串resize成可以装下答案字符串的长度

让快指针指向倒数原串的末尾，让慢指针指向新的字符串长度的末尾

快慢指针不断往后移动

当快指针指向的是字符时，就让慢指针将指向的位置改成字符

当快指针指向的是空格时，就让慢指针将指向的位置与后两个位置分别改成‘0’ ‘2’ ‘%’，然后慢指针-2迭代