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

1. 문제

 

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

 

 

 

2. 요구사항

1) 두 개의 문자열 haystack과 needle이 주어진다.

2) haystack에서 needle과 같은 문자열이 있는 경우에 처음 나타나는 인덱스를 반환한다.

3) 만약 일치하는 문자열이 없는 경우에는 -1을 반환한다.

 

 

3. 핵심 아이디어

1) substring으로 문자열 나누기

 

haystack을 needle과 비교하기 위해서 needle과 같은 문자열로 나눈 후, 비교해야 합니다.

 

str.substring(i, j)는 str 문자열을 i번째부터 j-1번째까지 나눕니다.

 

이렇게 나누어진 문자열과 needle을 비교한 후, 일치하면 해당 문자열의 첫 번째 인덱스를 반환하고,

문자열을 순회했음에도 일치하지 않는다면 -1을 반환합니다.

 

 

2) substring 코드

// 문자열을 순회하면서 needle과 같은 문자열을 찾는다.
// 비교하는 문자열은 substring으로 문자열을 나눈 후, 비교한다.
// str.substring(i, j) : 문자열을 i번째부터 j-1번째까지 나눈다.

class Solution {
  int strStr(String haystack, String needle) {
    for (int i = 0; i < haystack.length - needle.length + 1; i++) {
      if(haystack.substring(i, i + needle.length) == needle) {
        return i;
      }
    }
    return -1;
  }
}

 

시간 복잡도 : O(NM)

- O(N) : haystack.length - needle.length 만큼 문자열을 순회함

- O(M) : substring(i, i + M) 호출 -> substring은 길이가 M인 부분 문자열을 생성하는데 O(M) 시간이 걸림

 

공간 복잡도 : O(M)

- substring(i, i +M)을 호출할 대마다 길이가 M인 새로운 문자열이 생성됨

 

3) indexOf로 문자열 비교

 

str.indexOf(x)는 x문자열이 str 내에서 처음 등장하는 인덱스를 반환합니다. 없으면 없으면 -1을 반환합니다.

 

 

4) indexOf 코드

class Solution {
  int strStr(String haystack, String needle) {
    return haystack.indexOf(needle);
  }
}

 

시간 복잡도 : O(N + M)

- indexOf 메서드는 내부적으로 KMP 알고리즘을 사용함

- O(M) : needle의 접두사와 접미사가 일치하는 부분을 이용하여 매칭 테이블 생성

- O(N) : haystack을 한 글자씩 탐색하면서 needle과 비교

 

공간 복잡도 : O(1)

- 추가적인 배열이나 데이터 구조를 사용하지 않음