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

---

Description

Easy
Topics
Companies
Given two strings and , return the index of the first occurrence of in , or if is not part of .needlehaystackneedlehaystack-1needlehaystack

 

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 <= 104
haystack and consist of only lowercase English characters.needle

---

Code

func strStr(haystack string, needle string) int {
	if len(haystack) < len(needle) {
		return -1
	}


	for i := 0; i < len(haystack); i++ {
		if i+len(needle) <= len(haystack) && needle == haystack[i:i+len(needle)] {
			return i
		}
	}

	return -1
}

시간 복잡도 분석

1. 초기 조건 확인:
   • len(haystack) < len(needle)을 확인하는 부분은 상수 시간 O(1)입니다.
2. 주 반복문:
   • for i := 0; i < len(haystack); i++ 반복문은 haystack 문자열을 순회합니다.
   • haystack의 각 위치에서 길이가 needle과 같은 서브스트링을 비교하는데, 이 비교 연산은 O(m)입니다. 여기서 m은 needle의 길이입니다.
   • 따라서, 전체 반복문은 최악의 경우 O(n * m)입니다. 여기서 n은 haystack의 길이입니다.