手工实现一个字符串内容替换方法来替换replace
手工实现一个字符串内容替换方法来替换replace
前言
在遇到字符串替换的场景上replace方法跟replaceAll方法是最常用的解决办法，那如果让你手动处理字符串替换你会怎么做呢？
《剑指Offer》的05题就是这样一道：
如果使用replace方法一行代码就处理完毕
class Solution {
public String replaceSpace(String s) {
return s.replace(" ","%20");
}
}如果让我自己实现的话，代码如下：
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);
}
}执行结果：
分析
我上面的代码在复杂度上并没有太多优化，就是初始的考虑了怎么实现，现在来分析一下替换字符串的思路。
首先字符串是一个字符数组构成的，也就是char[]，以字符串“We are happy.”为例，结构如下图：
字符串带上空格有13个字符，空格的char为32，如果要将空格字符替换成%20就肯定需要增加char数组长度，一个字符变成三个字符就需要在原有char数组上增加两个字符长度，两个空格就是四个，结构就变成了下图：
所以到此有四个长度需要获取计算：
- 原始字符串长度
- 替换字符串的长度
- 被替换字符串的长度
- 新字符串的长度
前三个都是可以直接获取的，第四个需要计算，计算公式为：
原始字符串长度 + (被替换字符串长度 - 替换字符串长度) * 替换字符串数量
以上面的字符串进行公式计算：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];
}这四个数值得到后就是向新字符串数组填充内容，需要一个计数原始字符串的遍历位数一个记录新字符串的遍历位数，如果新字符串长度>旧字符串长度时在遇到替换字符串时新字符串的遍历位数+(被替换字符串长度 - 替换字符串长度) ，反之新字符串长度<旧字符串长度时遇到替换字符串时旧字符串的遍历位数+(被替换字符串长度 - 替换字符串长度) 。
这里%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和判断空字符串条件32替换为被替换字符串长度跟char值就能通用多个字符串跟标准字符串。
腾讯云开发者
