리트코드 - 28. Find the Index of the First Occurrence in a String

리트코드 - 28. Find the Index of the First Occurrence in a String

출처 - https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

두 개의 문자열 needle과 haystack이 주어졌을 때, haystack 안에서 needle의 첫 번째 발생 위치(index)를 반환하거나, needle이 haystack에 포함되어 있지 않으면 -1을 반환합니다.

 

의사코드

index = -1 c = needle의 첫번쨰 글자를 character로 저장 반복문 시작 (haystack을 한글자씩 순회)     if (index + needle 길이 <=  haystack의 길이 && c == haystack 순회하는 글자)         cut = haystack을 순회하는 글자부터 needle길이만큼 자름             if (cut이 needle과 같으면)             index = 반복문의 인덱스             break         else             continue 반복문 종료 index 리턴

 

풀이코드

class Solution {
    public int strStr(String haystack, String needle) {
        int index = -1;
        char c = needle.charAt(0);

        for (int i = 0; i < haystack.length(); i++) {
            if (i + needle.length() <= haystack.length() && c == haystack.charAt(i)) {
                String cut = haystack.substring(i, i + needle.length());

                if (cut.equals(needle)) {
                    index = i;
                    break;
                } else {
                    continue;
                }
            }
        }
        return index;
    }
}

코드설명

바늘 속에서 건초찾기라는 속담을 구현(?)한 문제이다.

먼저 needle의 첫번째 값을 잘라서 c로 놓고 기준값으로 삼아, haystack이 그 값을 가지는지 찾는다.

 

반목문에서는 haystack을 한 글자씩 순회하는데, c와 같은 값이 나오면 그 인덱스부터 needle의 길이만큼 문자열을 자른다.

이 자른 값을 needle과 비교하여 같으면 이 때의 인덱스로 갱신해주고 break 하면 된다.

 

단, 이 값을 자를때 haystack보다 크게 잘라질 가능성이 있으므로 조건을 걸어주어야 한다.

예를 들어 haystack = "aabcb" 이고, needle="bccc" 라고 한다면

needle의 첫번째인 b를 기준으로 찾기 때문에 haystack을 잘라내면 StringOutOfRange가 발생한다.

 

따라서 자르는 길이에 대한 조건을 haystack의 크기보다는 작을때까지만 잘라주어야 한다.

 

그래서 if문에 i + needle.length() <= haystack.length() 가 추가되었다.

 

시간복잡도 - O(n * k). (n은 haystack의 길이, k는 needle의 길이)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

substring을 사용할 때 항상 string을 벗어나지 않도록 해야한다.

 

다른코드

class Solution {
    public int strStr(String haystack, String needle) {
        int hLen = haystack.length();
        int nLen = needle.length();
        int nIndex = 0;
        for(int i=0; i<hLen; i++){
            // as long as the characters are equal, increment needleIndex
            if(haystack.charAt(i)==needle.charAt(nIndex)){
                nIndex++;
            }
            else{
                // start from the next index of previous start index
                i=i-nIndex;
                // needle should start from index 0
                nIndex=0;
            }
            // check if needleIndex reached needle length
            if(nIndex==nLen){
                // return the first index
                return i-nLen+1;
            }
        }
        return -1;
    }
}

이 코드는 슬라이드 윈도우 방식으로 비교하고 있다.

실제로 담는 배열이 있는 것은 아니지만 가상의 담는 공간이 있는것처럼 두 char값이 일치하면 추가하고,

다르면 다시 원래의 반복순회하던 값으로 돌아간다.

 

else분기의 i = i - nIndex는 이를 위한 코드인데, 상당히 인상적이다.

 

정리

substring 사용 시 범위를 넘지 않게 주의할 것