前言
今天上网浏览网站的时候 , 看到一个一个问题, 问题是这样的 “A、 B 、 C 是 3 个字符串。把 A 中包含的所有 B 都替换为 C ，如果替换以后还有 B 就继续替换，直到 A 不包含 B 为止。”
乍一看, 这不是挺简单的么 . 仔细一看, 题目后面还有一行小字
请编写程序实现以上功能。不允许使用系统提供的字符串比较、查找和替换函数。
这就有点意思了, 我们日常编写代码, 字符串查找替换函数使用的都是系统提供的标准方法 , 一点问题都没有, 但如果让我们自己实现一个呢 . 有时候还真不是很简单.
如何实现
要实现替换, 首先要查找到开始替换的位置 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// 查找b在a中第一次出现的位置
func index(a,b string) int{
m,n := len(a),len(b)
if n == 0 {return 0} // b为空, 则返回0
if n > m {return -1} // b比a还长, 则返回-1
for i := 0; i < m-n+1; i++ {
// 从a的第一位开始, 判断是否有子串和b完全相同, 有的话返回索引位置
if a[i] == b[0] {
if a[i:i+n] == b[:]{
return i
}
}
}
return -1 // 没有匹配到, 也返回-1
}
|
ok , 现在位置有了, 我们可以实现将a中的b, 替换成c
1
2
3
4
|
func replaceIndex(a,b,c string,index int)string{
n := len(b) // b的长度
return a[0:index] + c + a[index+n:] // 拼接字符串, 完成替换
}
|
现在最重要的部分都有了, 可以完成全部的逻辑了, 只需要循环就可以了
1
2
3
4
5
6
7
8
9
10
11
|
func final(a,b,c string)string{
if index(c,b) > 0 {return ""} // 这里需要注意, 如果c中包含b, 则永远无法完成替换, 这个是错误的
if index(a,b) > 0 {
for{
i := index(a,b)
if i <= 0 {return a} // 循环到找不到b结束
a := replaceIndex(a,b,c,i)
}
}
return ""
}
|
结束
至此就实现了题目中的要求, 其实go的标准库中实现挺复杂的, 考虑到了各种长度字符串的情况, 还使用到了rabin-karp算法 . 可见一个简单的问题, 如果完全不使用库也不是那么容易 .
那么我们写代码需要了解到各种标准库的实现吗 ? 这是个问题 .
