图解剑指 offer 第二题： 替换空格

题目描述

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

题目解析

这是一道很容易理解也很好简单粗暴解决的问题。

对于很多编程语言而言，都内置了”替换“方法。只需要简单的调用 API 即可。

比如：

return str.toString().replaceAll("\s", "%20");

但，你有看过 replaceAll 的源码实现么。

return Pattern.compile(regex).matcher(this).replaceAll(replacement);

public String replaceAll(String replacement) {
        reset();
        boolean result = find();
        if (result) {
            StringBuilder sb = new StringBuilder();
            do {
                appendReplacement(sb, replacement);
                result = find();
            } while (result);
            appendTail(sb);
            return sb.toString();
        }
        return text.toString();
    }

即使你不懂 Java，看到关键字 regex，也能猜出这个源码的实现使用了 正则表达式，并且同时实现代码里面不停的创建与销毁对象，性能方面很不理想。

对于此题，我们只需要去寻找可以被替换的部分，然后把不被替换的部分和替换者一个个连接起来就行了，远远不需要这么复杂的操作。

解法

解法一：遇山开山,遇水架桥

题目要求我们将空格替换掉，那么完全可以从前往后依次遍历字符串，遇到空格替换即可。

使用这种解法在每一次碰到空格字符的时候都做替换，并且由于是把 1 个字符替换成 3 个字符，那么每次替换一个空格后都需要把空格后面所有的字符都后移两个字节，否则就有两个字符被覆盖。

假设字符串的长度是 n 。对每个空格字符，需要移动后面 O(n) 个字符，因此对含有 O(n) 个空格字符的字符串而言总的时间复杂度是 O(n^2) 。

解法二：山不转水转

通过指针（水）将字符（山）搬动。

首先遍历一次字符串，统计出字符串中空格的总数，同时计算出替换之后的字符串的总长度。

以前面的字符串”We Are Happy.”为例，”We Are Happy”这个字符串的长度是14（包括结尾符号’’），里面有两个空格，因此替换之后字符串的长度是 14 - 2 + 2 * 3 = 18 。

接下来就是 解法二 的精髓所在：从字符串的后面开始复制和替换。

首先，申请长度为 18 的空间。

接下来，定义两个指针：P1 和 P2 。

其中指针 P1 指向原始字符串的末尾，指针 P2 指向替换之后的字符串的末尾。

然后将指针 P1 向前移动，逐个把它指向的字符复制到指针 P2 指向的位置。

当碰到空格的时候，指针 P1 先不动，挪动指针 P2 的位置并赋值 %20 ，然后再同时向前移动并复制。

解法三：人造山

这种解法与 解法二 类似，唯一的不同点在于需要 重新开辟 一个新的数组进行数据的存放。

代码如下：

//解题地址：https://www.nowcoder.com/ta/coding-interviews?query=&asc=true&order=&page=1
public class Solution {
    public String replaceSpace(StringBuffer str) {
       String str1 = str.toString();
        if(str1.equals(""))
            return str1;
        char [] strArray = str1.toCharArray();
        int i =0;
        int lengthSpace = 0;
        while(i < strArray.length){
           if(strArray[i] == ' ')
               lengthSpace++;
           i++;
       }
        int newStrLength = strArray.length + lengthSpace*2;
        char [] newStr = new char[newStrLength];
        int j = newStrLength-1;
        i = strArray.length - 1;
        while(i >= 0){
            if(strArray[i] !=  ' '){
             newStr[j--] = strArray[i--];
           }else{
               newStr[j--] = '0';
               newStr[j--] = '2';
               newStr[j--] = '%';
               i--;
           }
       }
       return new String(newStr);
    }
}

总结

解法二 与 解法三 的时间复杂度都为 O(n) 级别，对比 解法一 而言，事实上思考逻辑改变的东西不多，效率却高了一个数量级，这大概就是 算法的魅力 吧。