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%
funcstrStr(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) } }forlen(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}
在解答看到的另一個精妙的解法:
funcstrStr(haystack string, needle string) int {if needle =="" {return0 }// Find the index of the needle in the haystack index := strings.Index(haystack, needle)// Return the index, or -1 if the needle was not foundif index >=0 {return index } else {return-1 }}