[Top Interview Questions] 28. Find the Index of the First Occurrence in a String

정답)

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # needle의 길이 만큼의 문자열을 haystack에서 검색
        for i in range(len(haystack) - len(needle) + 1):
            
            # 그 문자열이 needle과 같다면
            if haystack[i:i+len(needle)] == needle:
                return i

        return -1

문제)

문제출처

 

주어진 문자열 haystack과 needle을 사용하여,

haystack에서 needle이 처음 발견되는 index를 리턴하거나

haystack에 needle이 존재하지 않는다면 -1을 리턴하시오.

 

예시 1)

haystack = "sadbutsad", needle = "sad"

output = 0

"sad"가 0번째, 6번째 index에 존재합니다. 처음 발견되는 index를 리턴해야 됨으로 0을 리턴.

 

예시 2)

haystack = "leetcode", needle = "leeto'"

output = -1

"leeto"가 "leetcode"에 존재하지 않음으로 -1을 리턴.

 

제한)

 

• 1 <= haystack과 needle의 길이 <= 10^4
• haystack과 needle은 오직 영어 소문자로만 이루어져 있습니다.

풀이)

for문을 몇 번?)

needle이 haystack에 존재하는지 확인하려면 haystack을 선형검색해야됩니다.

그래서 저는 for문을 사용할 것인데 몇 번을 해야 되는 걸까요?

 

평소처럼 for i in range(len(haystack))을 사용하면 안 됩니다.

index out of range가 발생할 수도 있기 때문이죠.

 

저희는 평소처럼 한 문자 한 문자 검색하는 것이 아닌 needle의 길이만큼의 문자열을 검색할 것입니다.

그래서 아래 그림 같은 상황에서 haystack에 존재하지 않는 index의 문자를 찾다가 오류가 발생할 수도 있습니다.

 

8번과 9번은 index out of range 에러

그래서 index out of range 오류를 방지하기 위해 아래와 같이 적어줍니다.

 

len(haystack) - len(needle) + 1

def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack) - len(needle) + 1):

Slicing)

위에서 needle의 길이만큼의 문자열을 haystack에서 확인한다고 했습니다.

 

원하는 길이만큼의 문자열을 어떻게 확인할까요?

바로 Slicing(슬라이싱)입니다. 

 

예를 들어 needle의 길이가 3입니다. 그럼 haystack에서 3만큼의 문자열을 확인하기 위해서는 haystack[i : i+3]을 사용하면 됩니다. 이렇게 되면 i번째 문자를 포함하는 3개의 문자를 확인할 수 있습니다. 

 

haystack[i : i+len(needle)]

만약 이 방식으로 3개의 문자가 needle과 동일하다면 맨 앞 index i를 리턴하면 됩니다.

모든 문자열이 needle과 동일하지 않다면 for문이 끝나고 -1을 리턴하면 되겠죠.

 

def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i:i+len(needle)] == needle:
                return i

        return -1

디버깅)

haystack = "haystack", needle = "stac"

 

(i=0)    # hays != stac

(i=1)    # ayst != stac

(i=2)    # ysta != stac

 

(i=3)

"stac" = "stac"

return 3

 

이번 문제도 코드는 꽤나 깔끔하게 적힌 것 같습니다. 물론 이거보다 더 아름답게 쓰시는 분들도 계시겠죠.

원리를 빨리 알아내고 숫자 계산이 빨리빨리 된다면 나름 직관적이었다고 생각합니다. 제대로 이해되셨으면 좋겠네요!

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)