[LeetCode] 28. Find the Index of the First Occurrence in a String (Python)

Top Interview 150

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

Easy

---

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

---

Code

class Solution(object):
    def strStr(self, haystack, needle):
        for i in range(len(haystack)):
            if haystack[i : i+len(needle)] == needle:
                return i
        return -1

haystack이라는 문자열 내부에 needle이라는 문자열이 존재하는지 확인하는 문제이다.

만약 존재한다면, needle이 등장하는 시작 인덱스를 반환한다. 존재하지 않는다면, -1을 반환한다.

나는 haystack[i : i+len(needle)] == needle로 haystack 내부를 탐색하여 존재 여부를 결정했다.

Time Complexity

• for문 순회: $O(N)$
• haystack 슬라이싱: $O(M)$