作者 | 陌无崖
转载请联系授权
题目要求解题思路蛮力轮询排序后轮询
给定一个长字符串a和短字符串b,高效判断短字符串b中的所有字符是否都在长字符串中 如:
a := "ABCD"
b := "BAD"//输出true
a := "ABCD"
b := "BAE"//false
a := "ABCD"
b := "AA" //true
对于此类题目,通常解决起来并不难,利用Golang中的contains()函数的辅助可以快速编写成功,为了更好的理解,我们不使用contain()函数。
轮询短字符串b中的每一个字符,逐个进行和长字符串进行比较,代码如下:
func StringContain(a string, b string) bool {
ar := []rune(a)
br := []rune(b)
// 用短字符串去寻找长字符串进行比较,因此主循环用短字符串进行控制
for i := 0; i < len(br); i++ {
// 定义一个 j 用来每次循环都要保证从 0 开始,j 代表 ar的下表
j := 0
// 循环长字符串
for j = 0; j < len(ar) && br[i] != ar[j]; j++ {
}
// 如果在遍历的过程中遇到不符合情况的字符,则上一个循环会比较到 ar 最后,可用 j 作为判断
// 如果在循环的过程中找到相同字符,第二个循环会提前结束
if j > len(ar) {
return false
}
}
return true
}
对字符串进行排序,然后再对字符串进行依次轮询,我们使用快速排序的方法,为了简单,我们直接使用Go语言的sort包的Sort方法,需要实现相应的接口,首先我们需要自定义一个类型
type RuneSclice []rune
然后用该类型实现相关接口
func (p RuneSclice) Len() int {
return len(p)
}
func (p RuneSclice) Less(i, j int) bool {
return p[i] < p[j]
}
func (p RuneSclice) Swap(i, j int) {
p[i], p[j] = p[j], p[i]
}
编写判断字符串是否包含的函数
func StringSortContain(a string, b string) bool {
ar := []rune(a)
var ars RuneSclice
ars = ar
br := []rune(b)
var brs RuneSclice
brs = br
// 排序
sort.Sort(ars)
sort.Sort(brs)
// 定义两个指针分别指向ars和brs
pa := 0
pb := 0
for pb < brs.Len() {
// 移动pa指针寻找相同的字符,pb暂时不移动
for (pa < ars.Len()) && (ars[pa] < brs[pb]) {
pa += 1
}
// 说明pa遍历结束仍然未找到,存在不相同的字符,返回false
if pa >= ars.Len() || ars[pa] > brs[pb] {
return false
}
// 说明找到了相同的,开始寻找下一个,pb向后移动
pb += 1
}
return true
}