28. Find the Index of the First Occurrence in a String

Medium
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
Constraints:
  • 1 <= haystack.length, needle.length <= 10^4
  • haystack and needle consist of only lowercase English characters.
​

解題

Runtime: 0 ms, faster than 100%
Memory Usage: 2 MB, less than 36.4%
func strStr(haystack string, needle string) int {
queue := []int{} // 把 haystack 中和 needle[0] 相同字元的 index 存入
for i := 0; i <= len(haystack) - len(needle); i++ {
if haystack[i] == needle[0] {
queue = append(queue, i)
}
}
​
for len(queue) != 0 {
index := queue[0]
queue = queue[1:]
for i := 0; i < len(needle); i++ {
if haystack[i+index] != needle[i] {
break
}
​
if i == len(needle) - 1 {
return index
}
}
}
​
return -1
}
在解答看到的另一個精妙的解法:
func strStr(haystack string, needle string) int {
if needle == "" {
return 0
}
// Find the index of the needle in the haystack
index := strings.Index(haystack, needle)
// Return the index, or -1 if the needle was not found
if index >= 0 {
return index
} else {
return -1
}
}