网站被收录要怎么做,做网站付多少定金,网站建设功能报价,dw网站建设素材实现 strStr() 函数。
给你两个字符串 haystack 和 needle #xff0c;请你在 haystack 字符串中找出 needle 字符串出现的第一个位置#xff08;下标从 0 开始#xff09;。如果不存在#xff0c;则返回 -1 。
说明#xff1a;
当 needle 是空字符串时#xff0c;我们…实现 strStr() 函数。
给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串出现的第一个位置下标从 0 开始。如果不存在则返回 -1 。
说明
当 needle 是空字符串时我们应当返回什么值呢这是一个在面试中很好的问题。
对于本题而言当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1
输入haystack “hello”, needle “ll” 输出2 示例 2
输入haystack “aaaaa”, needle “bba” 输出-1 示例 3
输入haystack “”, needle “” 输出0
解题思路
先生成next数值再用模式串和目标串进行匹配如果遇到不匹配的字母则模式串的指针直接移到到next数值指向的位置再次进行匹配如果不匹配再次进行相同的动作直到j指针为0即指向模式串的开头或者字符匹配上了
代码
func strStr(haystack string, needle string) int {n,m: len(haystack),len(needle)if m0{return 0}next:make([]int,m)for i,j : 1,0; i m; i {for j0needle[i]!needle[j] {jnext[j-1]}if needle[i]needle[j]{j}next[i]j}for i,j: 0,0; i n; i {for j0needle[j]!haystack[i] {jnext[j-1]}if needle[j]haystack[i]{j;}if jm{return i-m1}}return -1
}
