剑指Offer:替换空格

题目描述

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

分析

我们可以另申请一个StringBuffer对象 sb(动态字符),遍历一遍字符串。如果遇到空格就在sb的后面append三个字符‘%’、‘2’、‘0’,否则就将原字符append在sb的后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public String replaceSpace(StringBuffer str) {
if (str == null) return null;

StringBuffer string = new StringBuffer();
for(int i = 0; i < str.length(); i ++) {
if (str.charAt(i) == ' ') {
string.append('%');
string.append('2');
string.append('0');
} else {
string.append(str.charAt(i));
}
}
return string.toString();
}
}

我们也可以用另一种思路,我们先遍历一次字符串,这样就能统计出替换之后的字符串的总长度。每替换一个空格,长度增加2 。

我们从字符串的后面开始替换。申请两个指针p1和p2 。p1指向原字符串的末尾,p2指向替换之后的字符串的末尾。接着向前移动指针p1,逐个把它指向的字符复制到p2指向的位置,如果碰到空格,我们把p1向前移动1格,并把p2向前移动3格插入‘%20’。

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
void ReplaceBlank(char[] string, int length){  // length为字符串的总容量
if (string == null || length <= 0)
return ;
int originalLength = 0; // 字符串的实际长度
int numberOfBlank = 0;
int i = 0;
while(string[i] != "\0"){
++ originalLength;
if (string[i] == " ")
++ numberOfBlank;
++ i;
}

int newLength = originalLength + numberOfBlank*2;
if (newLength > length)
return ;

int indexOfOriginal = originalLength;
int indexOfNew = newLength;
while(indexOfOriginal >= 0 && indexOfNew >= 0){
if (string[indexOfOriginal] == " "){
string[indexOfNew --] = '0';
string[indexOfNew --] = '2';
string[indexOfNew --] = '%';
} else{
string[indexOfNew --] = string[indexOfOriginal];
}
-- indexOfOriginal;
}
}