# 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:
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 相同字元的 index 存入
for i := 0; i <= len(haystack) - len(needle); i++ {
if haystack[i] == needle {
queue = append(queue, i)
}
}
for len(queue) != 0 {
index := queue
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
}
}