替换空格

  • 题目描述:

请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

  • 解题思路:

如果直接对源字符串进行搜索,每次遇到空格时便将其替换成给定的3个字符,由于字符串长度会发生改变,所以空格后面的字符都需要进行移动,整个过程中字符移动的次数比较多。
我们可以预先找好空格的个数并扩展字符串长度,从后向前进行搜索,每个字符串确定好位置后不会再改变,这样效率会更高一些。

  • 源代码:
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
class Solution {
public:
void replaceSpace(char *str,int length) {
if (str == NULL || length < 0){
return;
}
int i = 0;
int spaceNum =0,oldlength = 0; //记录空格数和字符串初始长度
while (str[i] != '\0') { //遍历字符串,字符串末尾的'\0'作为结束判断条件
if (str[i] == ' ') {
spaceNum++; //记录字符串中空格的个数
}
oldlength++;
i++;
}
int newlength = oldlength + spaceNum*2; //扩展后字符串的长度
if (newlength > length) {
return; //如果替换空格后的长度大于字符串总长度,无法替换
}
while (oldlength >=0 && newlength > oldlength) { //字符串未遍历到首元素且依旧存在空格未被替换时
if (str[oldlength] == ' ') {
str[newlength--] = '0';
str[newlength--] = '2';
str[newlength--] = '%';
}
else {
str[newlength--] = str[oldlength]; //源字符串每个结点的位置都会唯一确定且不再改变
}
oldlength--;
}
}
};
-------------The End-------------