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

📌 문제 설명

문자열 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 알고리즘을 배우면 성능을 더 향상시킬 수 있음