[Leetcode] 28. Find the Index of the First Occurrence in a String - JS

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

 

 

1. 문제 분석

문제분석
--------------------
문자열 needle과 haystack이 주어진다.
haystack 안에서 needle이 첫번째로 등장하는 인덱스를 반환하라. 없으면 -1을 반환하라.

제한조건
--------------------
- 1 <= haystack.length, needle.length <= 10^4
- haystack, needle은 영어 소문자로만 구성된다.

 

2. 접근 방법

접근방법
--------------------
haystack 문자열을 순회하면서 needle이 존재하는지 비교한다.

 

 

3. 코드

var strStr = function(haystack, needle) {
    let index = -1;
    for (let i = 0; i <= haystack.length - needle.length; i++) {
        let word = haystack.slice(i, i + needle.length);
        if (needle === word) {
            index = i
            break;
        }
    }
    return index;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

slice를 활용하여 haystack의 인덱스에서 needle 과 동일한 길이의 단어를 비교했다. 문제를 읽자마자 떠오르는 쉬운 문제였다.