题目 LeetCode LeetCode-cn
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Example 1: Input: haystack = "hello", needle = "ll" Output: 2 Example 2: Input: haystack = "aaaaa", needle = "bba" Output: -1 Example 3: Input: haystack = "", needle = "" Output: 0 Constraints: 0 <= haystack.length, needle.length <= 5 * 104 haystack and needle consist of only lower-case English characters.
题解 难度简单。 这道题就是说要找到needle
在haystack
第一个出现的位置,如果没有出现就返回-1
。
解法一:暴力法 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 26 27 28 29 30 31 32 func strStr (haystack string , needle string ) int { if len (haystack) == 0 && len (needle) == 0 { return 0 } if len (haystack) == 0 { return -1 } if len (needle) == 0 { return 0 } if len (haystack) < len (needle) { return -1 } len_h := len (haystack) len_n := len (needle) for i:=0 ;i<len_h-len_n+1 ;i++ { j := 0 ; for ;j<len_n;j++ { if (haystack[i+j] != needle[j]) { break ; } } if (j == len_n) { return i; } } return -1 ; }
执行结果:
1 2 3 4 5 6 7 leetcode-cn: 执行用时:0 ms, 在所有 Go 提交中击败了100.00%的用户 内存消耗:2.2 MB, 在所有 Go 提交中击败了64.54%的用户 leetcode: Runtime: 0 ms, faster than 100.00% of Go online submissions for Implement strStr(). Memory Usage: 2.3 MB, less than 100.00% of Go online submissions for Implement strStr().
参考资料 Golang
中的内置函数strings.Index 也可以实现,可以参考它的源码实现。
1 2 3 4 5 import "strings" func strStr (haystack string , needle string ) int { return strings.Index(haystack,needle) }