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
	}
}