28. Find the Index of the First Occurrence in a String

2026-03-27
leetcode
리트코드 28번 풀이

문제

Find the Index of the First Occurrence in a String

풀이

아이디어

haystack 문자열에서 needle 문자열이 처음으로 등장하는 위치를 찾는 문제다. 투포인터를 이용해서 haystack 문자열을 순회하면서 needle 문자열과 일치하는지 확인하면 된다. haystack 문자열의 각 문자에 대해서 needle 문자열의 첫 번째 문자와 일치하는지 확인하고, 일치한다면 needle 문자열의 나머지 문자들과도 일치하는지 확인한다. 만약 일치한다면 해당 위치를 반환하고, haystack 문자열을 끝까지 순회해도 일치하는 부분이 없다면 -1을 반환한다.

코드

function strStr(haystack: string, needle: string): number {
  for (let left = 0; left <= haystack.length - needle.length; left++) {
    if (haystack[left] !== needle[0]) continue;
    let right = 0;
    while (haystack[left + right] === needle[right]) {
      right++;
      if (right === needle.length) return left;
    }
  }

  return -1;
}

시간 / 공간 복잡도

  • 시간 복잡도: O(n * m) — n: haystack 길이, m: needle 길이
  • 공간 복잡도: O(1)

여담

indexOf 메서드를 사용하면 더 간단하게 풀 수 있다.

function strStr(haystack: string, needle: string): number {
  return haystack.indexOf(needle);
}