[Dart] LeetCode 28. Find the Index of the First Occurrence in a String
1. 문제
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)
- 추가적인 배열이나 데이터 구조를 사용하지 않음