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)$的时间
原文链接: https://zijian.wang/2021/05/26/05. 替换空格/
版权声明: 转载请注明出处.