《剑指offer》 05.替换空格

剑指offer
留言

Note： 可能在面试的时候需要问清楚原字符串是否可以改动，可以的话我们利用c++ string的特性原地操作，不可以的话就需要重新new一个string。总之是一个很简单的题目，可能需要注意的是string的resize方法可以扩充string的大小

题目描述

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

解法一：不可修改原字符串

思路

new一个新的字符串，进行填充。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string replaceSpace(string s) {
        int len=s.length(),size;
        int count=0;
        for(auto c:s){
            if(c==' ')
                count++;
        }
        string ans = string(count*2+len,' ');
        for(int i=0,j=0;i<len;i++,j++){
            if(s[i]!=' '){
                ans[j] = s[i];
            }else{
                ans[j++] = '%';
                ans[j++] = '2';
                ans[j] = '0'; 
            }
        }
        return ans;
    }
};

复杂度

  • 时间复杂度$O(n)$。一定要遍历整个字符串的。
  • 空间复杂度$O(n)$。姑且将新建的字符串当作额外空间吧。如果不算那就$O(1)$

解法二：利用C++特性在原字符串上进行修改

思路

主要借助c++的string中的resize函数，来重新调整字符串大小，然后利用双指针，从后往前遍历填充，不会造成读写冲突。

代码

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
class Solution {
public:
    string replaceSpace(string s) {
        int len=s.size(),size;
        int count=0;
        for(auto c:s){
            if(c==' ')
                count++;
        }
        size = len+count*2;
        s.resize(size);
        
        for(int i=len-1,j=size-1;i>=0&&j>=0;i--,j--){
            if(s[i]!=' '){
                s[j] = s[i];
            }else{
                s[j] = '0';
                s[j-1] = '2';
                s[j-2] = '%';
                j -= 2;
            }
        }
        return s;
    }
};

复杂度

  • 时间复杂度$O(n)$。需要遍历整个字符串两次。
  • 空间复杂度$O(1)$。原地扩展字符串s。所以应该是$O(1)$的时间