[python3] 28. Find the Index of the First Occurrence in a String

풀이 일자: 23.03.03

난이도: [Medium]

분류: [Two Pointer, String, String Match]

문제 내용

문제의 내용으로는 needle과 haystack이라는 변수에 담긴 문자열이 주어졌을 때 needle이 haystack에 포함되는 경우 포함되는 부분의 첫 인덱스를 리턴하고 포함하지 않는 경우 -1을 리턴하는 문제다.

 

 

문제 해결 흐름

1. 간단하게 생각해보면 열심히 순회를 하면서 needle과 같은게 나오는지 확인하면 된다.(Sliding Window)

→ 조금 더 생각해보면 while문으로 돌려서 현재의 인덱스(i) + len(needle) <= len(haystack)까지만 돌리면 되겠다.

 

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        ans = -1;
        i = 0;
        while(i + len(needle) <= len(haystack)):
            if haystack[i: i + len(needle)] == needle:
                ans = i;
                break;
            i += 1;

        return ans;

=> 가장 간단하게 떠올릴 수 있는 방법

 

Time Complexity: O(nm)

haystack 내부의 문자를 거의 다 순회하고 내부에서 문자 비교를 하기에 nm이 시간복잡도가 되겠다.

 

Space Complexity: O(1)

몇 개의 변수만을 사용해서 풀었기 때문에 공간복잡도는 1이다.

 

2. 좀 더 나아간다면?

→ 우선 첫글자가 같은지 확인하고 전체를 비교하는 방법이 있겠다.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        ans = -1;
        i = 0;
        while(i + len(needle) <= len(haystack)):
            if haystack[i] == needle[0]:
                if haystack[i: i + len(needle)] == needle:
                    ans = i;
                    break;
            i += 1;

        return ans;

=> 유의미한 차이는 없으나 조금이라도 줄여보려는 노력

Time Complexity: O(nm)

haystack 내부의 문자를 거의 다 순회하고 내부에서 문자 비교를 하기에 nm이 시간복잡도가 되겠다.

 

Space Complexity: O(1)

몇 개의 변수만을 사용해서 풀었기 때문에 공간복잡도는 1이다.

 

3. Python에서 제공하는 내장함수를 사용해보자. 여러 언어에서 비슷한 문법으로 제공하고 있다.

→ 문제의 내용에 딱맞는 함수가 find라는 함수가 존재한다.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        pos = haystack.find(needle);
        return pos;

 

 

다른 해결 방식(Official Solution)

1. Simple한 방식의 Sliding Window뿐만 아니라 Rabin-Karp 알고리즘을 소개하고 있다.

→ 알고리즘 대회에서나 나올법한 알고리즘으로 대표적인 문자열 탐색 알고리즘이다.

 

해당 알고리즘을 간단히 소개한다면 문자열을 숫자형태의 해시값으로 변경하여 비교하는 방법이다.

 

현재 찾는 문자열의 해시값을 구한다고 하면,

s = "abcd";
b = "bc";

b의 해시값 = (98 - 97) * (26^1) + (99 - 97)*(26^0) = 28

 

1) s[0:2]의 해시값을 구해 같은지 확인한다.

s = "abcd";
b = "bc";

s[0:2] 해시값 = (97-97)*(26^1) + (98-97)*(26^0) = 1

b의 해시값 != s[0:2] 해시값

2) s[1:3]의 해시값을 구해 같은지 확인한다.

s = "abcd";
b = "bc";

s[1:3] 해시값 = s[0:2] 해시값 * 26 - s[0] 해시값 * (26^2) + s[2] 해시값
= s[0:2] 해시값 * 26 - s[0] * (26^2) + s[2]

b의 해시값 == s[0:2] 해시값

3) 해시충돌로 인해 같은게 나온건지 확인하기 위해 한 글자씩 비교하면 끝!

 

 

위의 알고리즘을 그대로 코드로 옮긴다면,

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        m = len(needle)
        n = len(haystack)
        if n < m:
            return -1

        RADIX = 26                        # 진수라고 생각하면 된다.
        MOD = 1_000_000_033               # 해싱을 하다보면 숫자가 너무 커지는 경우가 발생하여 MOD를 취한다.
        MAX_WEIGHT = 1

        for _ in range(m):                # needle의 자리수를 이용하여 최대 weight를 계산
            MAX_WEIGHT = (MAX_WEIGHT * RADIX) % MOD

        def hash_value(string):           # string의 해시값을 계산하는 함수
            ans = 0
            factor = 1

            for i in range(m - 1, -1, -1):
                ans += ((ord(string[i]) - 97) * (factor)) % MOD  #아스키코드로 몇번째 문자인지 계산 후에 factor를 곱한다.
                factor = (factor * RADIX) % MOD

            return ans % MOD              

        hash_needle = hash_value(needle)     # needle의 해시값을 계산하고

        for window_start in range(n - m + 1):
            if window_start == 0:            # 처음 시작하면 현재의 haystack의 해시값을 구한다.
                hash_hay = hash_value(haystack)
            else:                            # sliding window 알고리즘처럼 이전 문자의 해시값을 빼고 새로운 문자의 해시값을 더한다.
                hash_hay = ((hash_hay * RADIX) % MOD     # 이를 통해 연산이 중복되는 것을 줄인다.
                            - ((ord(haystack[window_start - 1]) - 97)
                            * MAX_WEIGHT) % MOD
                            + (ord(haystack[window_start + m - 1]) - 97)
                            + MOD) % MOD

            if hash_needle == hash_hay:       # 해시값이 같은 경우 해시충돌로 인한 것인지 확인을 위해 자리마다 확인
                for i in range(m):
                    if needle[i] != haystack[i + window_start]:
                        break
                if i == m - 1:
                    return window_start

        return -1

=> Rabin-Karp 알고리즘으로 복잡해보이지만 새로운 아이디어인 것 같다.

 

Time Complexity: O(nm)

haystack 내부의 문자를 거의 다 순회하고 내부에서 hash값이 같다면 문자 하나하나씩 직접비교가 일어나기 때믄에 nm의 시간복잡도를 가진다.

 

Space Complexity: O(1)

몇 개의 변수만을 사용해서 풀었기 때문에 공간복잡도는 1이다.

 

2. 위의 알고리즘은 단일 해시를 사용하여 풀었지만 문제는 해시 충돌로 인한 가짜 hit을 막기 위해 해시값이 같음에도 문자를 하나하나씩 직접 다시 확인해야 하는 문제가 존재한다.

→ 2중 해싱을 이용하여 하나하나 확인하는 과정을 생략할 수 있게 만들 수 있다. 이 내용에 대해서는 위의 설명을 이해했다면 아래의 링크를 타고 보면 이해하기 쉬울 것이다.

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/editorial/

 

 

문제 링크

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

Find the Index of the First Occurrence in a String - LeetCode