Go语言：基础练习–查找 substring 的函数

Go语言：基础练习–查找 substring 的函数

题目大意：实现一个查找 substring 的函数。如果在母串中找到了子串，返回子串在母串中出现的下标，如果没有找到，返回 -1，如果子串是空串，则返回 0 。

下文给出两种解法，一种是本人按照思路直接表达的写法，另一种是其他网友的写法，供对比学习。

解法一：

package main

import "fmt"

func findSubstring(s, sub string) int {
	if len(sub) == 0 {
		return 0
	}

	for i := 0; i < len(s); i++ {
		if s[i] == sub[0] && len(s)-i >= len(sub)-1 {  // 母字符串中如果有一个元素和子字符串的第一个元素相同，且这时，剩下的字符长度还大于子字符串，才继续判断
			//fmt.Println(s[i:len(sub)+i], sub)
			if s[i:len(sub)+i] == sub { //从母字符串中相同的那个字符串开始，截图跟字符串同样数量的字符串来比较，相等则认为找到了
				return i
			}
		}
	}
	return -1
}

func main() {
	s := "abbcsdfjh"
	sub := "hjhj"
	fmt.Println(findSubstring(s, sub))
}
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

解法二：

func strStr(haystack string, needle string) int {
	for i := 0; ; i++ {
		for j := 0; ; j++ {
			if j == len(needle) { // j循环次数直到len(needle)都没符合下面两种情况，说明找到了子字符串
				return i
			}
			if i+j == len(haystack) {  // 说明母字符串剩下的字符长度已经不可能包含子字符串了
				return -1
			}
			if needle[j] != haystack[i+j] {  // 在对比子字符串的过程中，没循环完（j最多能到len(needle)）就出现不相等的,就没必要比较这次了
				break
			}
		}
	}
}

// 内置包直接实现
func strStr1(haystack string, needle string) int {
	return strings.Index(haystack, needle)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20