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

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

 

https://youtu.be/Gjkhm1gYIMw?si=amLg-uiF5c1EAVDv

 

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # needle이 빈 문자열인 경우, 요구사항에 따라 0을 반환
        if needle == "":
            return 0

        # needle이 haystack에 포함되지 않으면, 바로 -1을 반환
        # 이 조건은 불필요한 반복을 줄여 효율성을 높여줌
        if needle not in haystack:
            return -1

        # haystack에서 needle을 검색하기 위해 반복문 시작
        # range(len(haystack) - len(needle) + 1): 마지막 위치까지 포함하여 순회
        # (마지막 비교 위치를 포함하기 위해 +1을 추가)
        for i in range(len(haystack) - len(needle) + 1):
            # needle과 haystack의 현재 위치(i)에서 비교를 시작
            for j in range(len(needle)):
                # haystack[i+j]와 needle[j]가 다르면 비교 중단
                # 이 위치에서 needle은 매칭되지 않음
                if haystack[i + j] != needle[j]:
                    break
                
                # needle의 모든 문자(j)가 일치했을 경우
                # 즉, 마지막 문자까지 성공적으로 비교한 경우 시작 위치 i를 반환
                if j == len(needle) - 1:
                    return i

        # needle이 haystack에 포함되지 않은 경우 -1 반환
        return -1

 

왜 range(len(haystack) - len(needle) + 1)인가?

간단한 요약

• range(len(haystack) - len(needle)): 마지막 위치를 비교하지 않음.
• range(len(haystack) - len(needle) + 1): 마지막 위치까지 포함하여 모든 경우를 비교.

 

코드 좀 더 최적화 하면, 

 

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == "":
            return 0

        if needle not in haystack:
            return -1

        for i in range(len(haystack) - len(needle) +1):
            if haystack[i: i+len(needle)] == needle:
                return i
        return -1