手工实现一个字符串内容替换方法来替换replace

前言

在遇到字符串替换的场景上replace方法跟replaceAll方法是最常用的解决办法，那如果让你手动处理字符串替换你会怎么做呢？

《剑指Offer》的05题就是这样一道：

如果使用replace方法一行代码就处理完毕

class Solution {
    public String replaceSpace(String s) {
        return s.replace(" ","%20");
    }
}
1
2
3
4
5

如果让我自己实现的话，代码如下：

class Solution {
    public String replaceSpace(String s) {
        byte[] cs = s.getBytes();
        byte[] addByte = "%20".getBytes();
        int addIndex = 0;
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] == 32){
                addIndex = addIndex + (addByte.length-1);
            }
        }

        char[] c = new char[cs.length+addIndex];
        int f = 0;
        for (int i = 0; i < c.length; i++) {
            if (cs[f] == 32){
                for (int j = 0; j < addByte.length; j++) {
                    c[i+j] = (char) addByte[j];
                }
                i = i+(addByte.length-1);
            }else{
                c[i] = (char) cs[f];
            }
            f++;
        }
        return new String(c);
    }
}
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

执行结果：

分析

我上面的代码在复杂度上并没有太多优化，就是初始的考虑了怎么实现，现在来分析一下替换字符串的思路。

首先字符串是一个字符数组构成的，也就是char[]，以字符串“We are happy.”为例，结构如下图：

字符串带上空格有13个字符，空格的char为32，如果要将空格字符替换成%20就肯定需要增加char数组长度，一个字符变成三个字符就需要在原有char数组上增加两个字符长度，两个空格就是四个，结构就变成了下图：

所以到此有四个长度需要获取计算：

1. 原始字符串长度
2. 替换字符串的长度
3. 被替换字符串的长度
4. 新字符串的长度

前三个都是可以直接获取的，第四个需要计算，计算公式为：

原始字符串长度 + (被替换字符串长度 - 替换字符串长度) * 替换字符串数量

以上面的字符串进行公式计算：13 + (3 - 1) * 2 = 17 结果17跟上面图片的长度一致

代码实现

因为替换字符串已知是空格所以固定1位字符，上面的四个长度获取三个即可，被替换字符的位数也需要额外计算一次。

代码如下：

    public String replaceSpace(String s) {
        // 获取原始字符串长度
        byte[] sb = s.getBytes();
        // 获取替换字符串长度
        byte[] addByte = "%20".getBytes();
        // 计算被替换字符串出现次数
        int addIndex = 0;
        for (int i = 0; i < sb.length; i++) {
            if (sb[i] == 32){
                addIndex++;
            }
        }
        // 计算新字符串长度
        char[] c = new char[sb.length+(addByte.length-1)*addIndex];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这四个数值得到后就是向新字符串数组填充内容，需要一个计数原始字符串的遍历位数一个记录新字符串的遍历位数，如果新字符串长度>旧字符串长度时在遇到替换字符串时新字符串的遍历位数+(被替换字符串长度 - 替换字符串长度) ，反之新字符串长度<旧字符串长度时遇到替换字符串时旧字符串的遍历位数+(被替换字符串长度 - 替换字符串长度) 。

这里%20 > ''所以新字符串的遍历位数+(被替换字符串长度 - 替换字符串长度) ，代码如下：

    public String replaceSpace(String s) {
        // 获取原始字符串长度
        byte[] sb = s.getBytes();
        // 获取替换字符串长度
        byte[] addByte = "%20".getBytes();
        // 计算被替换字符串出现次数
        int addIndex = 0;
        for (int i = 0; i < sb.length; i++) {
            if (sb[i] == 32){
                addIndex++;
            }
        }
        // 计算新字符串长度
        char[] c = new char[sb.length+(addByte.length-1)*addIndex];

        // 记录旧字符串遍历位数
        int f = 0;
        // 循环新字符串
        for (int i = 0; i < c.length; i++) {
            if (sb[f] == 32){
                for (int j = 0; j < addByte.length; j++) {
                    c[i+j] = (char) addByte[j];
                }
                // 遇到替换字符串新字符遍历位数跳过(被替换字符串长度 - 替换字符串长度) 
                i = i+(addByte.length-1);
            }else{
                c[i] = (char) sb[f];
            }
            f++;
        }
        return new String(c);
    }
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

按上面的公式把1和判断空字符串条件32替换为被替换字符串长度跟char值就能通用多个字符串跟标准字符串。