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

Problem #

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

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().

Problem Summary #

Implement a function to find a substring. If the substring is found in the original string, return the index where the substring appears in the original string; if it is not found, return -1; if the substring is an empty string, return 0.

Solution Approach #

This problem is relatively simple; just implement it directly.

Code #

package leetcode

import "strings"

// Solution One
func strStr(haystack string, needle string) int {
	for i := 0; ; i++ {
		for j := 0; ; j++ {
			if j == len(needle) {
				return i
			}
			if i+j == len(haystack) {
				return -1
			}
			if needle[j] != haystack[i+j] {
				break
			}
		}
	}
}

// Solution Two
func strStr1(haystack string, needle string) int {
	return strings.Index(haystack, needle)
}