반응형
📌 문제 설명
문자열 haystack에서 부분 문자열 needle이 처음으로 등장하는 인덱스를 찾아 반환하는 문제입니다.
🔹 문제 해석
주어진 두 문자열 needle과 haystack이 있을 때, haystack에서 needle이 처음으로 등장하는 인덱스를 반환하라. 만약 존재하지 않으면 -1을 반환하라.
🔹 예시
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Input: haystack = "leetcode", needle = "leeto"
Output: -1
🔹 단어 정리
단어 의미
| haystack | 건초 더미 (전체 문자열) |
| needle | 바늘 (찾는 부분 문자열) |
| first occurrence | 첫 번째 등장 |
✅ 풀이 아이디어
- 부분 문자열 needle의 길이 len만큼 haystack을 슬라이딩 윈도우 방식으로 잘라서 비교
- 일치하는 순간 인덱스를 반환하고, 없으면 -1 반환
🔸 예외 처리
- needle이 빈 문자열이면 0 반환하는 것이 일반적 (LeetCode 기준)
반응형
✅ TypeScript 코드
export function strStr(haystack: string, needle: string): number {
const len = needle.length;
for (let i = 0; i <= haystack.length - len; i++) {
if (haystack.slice(i, i + len) === needle) {
return i;
}
}
return -1;
}
✅ 시간 및 공간 복잡도
항목 복잡도
| 시간 | O((N - M + 1) * M) |
| 공간 | O(1) |
- N: haystack의 길이
- M: needle의 길이
- 보통 대부분의 테스트 케이스에서 매우 빠르게 동작
✅ Jest 테스트 코드
describe("LeetCode 28: Find the Index of the First Occurrence in a String", () => {
it("returns 0 when needle is at the start", () => {
expect(strStr("sadbutsad", "sad")).toBe(0);
});
it("returns -1 when needle is not present", () => {
expect(strStr("leetcode", "leeto")).toBe(-1);
});
it("returns index when needle appears in the middle", () => {
expect(strStr("hello", "ll")).toBe(2);
});
it("returns 0 for empty needle", () => {
expect(strStr("abc", "")).toBe(0);
});
});
✅ 마무리 정리
- slice()로 부분 문자열 비교하며 탐색하는 간단한 슬라이딩 윈도우 방식
- 내장 함수 없이도 직접 구현 가능
- KMP 알고리즘을 배우면 성능을 더 향상시킬 수 있음
반응형
'Algorithm > LeetCode' 카테고리의 다른 글
| [LeetCode 125] Valid Palindrome - 유효한 회문 판단하기 (0) | 2025.03.26 |
|---|---|
| [LeetCode 68] Text Justification - 텍스트 양쪽 정렬 (0) | 2025.03.25 |
| [LeetCode 6] Zigzag Conversion - 지그재그 변환 (0) | 2025.03.22 |
| [LeetCode 14] Longest Common Prefix - 가장 긴 공통 접두사 구하기 (0) | 2025.03.21 |
| [LeetCode 151] Reverse Words in a String - 문자열 뒤집기 최적화 (0) | 2025.03.19 |
