《编程珠玑》字符串包含
作者 | 陌无崖
转载请联系授权
字符串包含
题目要求解题思路蛮力轮询排序后轮询
题目要求
给定一个长字符串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
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-12-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录