剑指Offer 5. 替换空格

题目

题目:请实现一个函数,把字符串中的每个空格替换成”%20”。

例如输入 “We are happy.”,则输出 “We%20are%20happy.”。

解法1[Java]:从后向前扫描并替换空格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public String replaceSpace(StringBuffer str) {
int p1 = str.length() - 1;
for (int i = 0; i <= p1; i++)
if (str.charAt(i) == ' ')
str.append(" ");

int p2 = str.length() - 1;
while (p1 >= 0 && p2 > p1) { //在完成最后一个空格的替换之后,p1等于p2
char c = str.charAt(p1--);
if (c == ' ') {
str.setCharAt(p2--, '0');
str.setCharAt(p2--, '2');
str.setCharAt(p2--, '%');
} else {
str.setCharAt(p2--, c);
}
}
return str.toString();
}
}

这个问题要求贴近底层的思考方式,直接对字符进行操作。

如果从前向后扫描空格然后把空格替换成 %20,那么就会导致这个空格之后字符需要整体向后移动,如果采用这种方式,那么时间复杂度会变成 $O(n^2)$。

从后向前扫描替换的话,先扫描一遍字符串,根据空格的数量在字符串的末尾先补充足够的空格,每遇到一个空格,就在末尾补充两个空格,这样扫描一遍下来,替换之后的字符串的总长度就会确定下来。

相关链接

  1. StringBuffer - Java Docs