수달씨의 개발공간

🔗 문제 링크: https://leetcode.com/problems/is-subsequence/

📌 문제 설명

두 문자열 s와 t가 주어졌을 때, 문자열 s가 t의 **부분 수열(subsequence)**인지 판별하는 문제입니다.

🔹 Subsequence란?

• 원래 문자열에서 일부 문자를 삭제하여 얻을 수 있는 문자열
• 문자의 상대적인 순서가 유지되어야 함
• 연속될 필요는 없음

예시:

• "abc" → "ahbgdc" 는 부분 수열 ✅
• "axc" → "ahbgdc" 는 부분 수열 ❌ (x가 순서상 없음)

✅ 해결 아이디어 - Two Pointers

문자열 s의 각 문자가 문자열 t 안에서 순서를 유지한 채 등장하는지만 확인하면 됩니다.

🔹 전략

• 두 포인터 i, j를 각각 t, s를 탐색하는 인덱스로 사용
• t[i] === s[j]면 j를 증가시켜 s의 다음 문자로 이동
• j === s.length에 도달하면 모든 문자가 매칭된 것이므로 true

✅ 구현 코드 (TypeScript)

export function isSubsequence(s: string, t: string): boolean {
  let j = 0;
  for (let i = 0; i < t.length && j < s.length; i++) {
    if (t[i] === s[j]) {
      j++;
    }
  }
  return j === s.length;
}

🧪 테스트 코드 (Jest)

describe("Easy 392: Is Subsequence", () => {
  it("returns true when s is a subsequence of t", () => {
    expect(isSubsequence("abc", "ahbgdc")).toBe(true);
  });

  it("returns false when s is not a subsequence of t", () => {
    expect(isSubsequence("axc", "ahbgdc")).toBe(false);
  });
});

📈 시간 및 공간 복잡도

항목 복잡도

✅ 마무리 정리

• 핵심은 s의 각 문자가 t 안에서 순서를 유지하며 존재하는지를 확인하는 것
• Two Pointers를 통해 한 번의 순회로 간단하게 해결 가능

📌 KMP란?

KMP(Knuth-Morris-Pratt) 알고리즘은 부분 문자열 검색(substring search)을 위한 알고리즘으로, 시간 복잡도 **O(N + M)**으로 매우 효율적입니다.

KMP는 비교 중 매칭 실패 시 불필요한 반복을 피하기 위해 "접두사-접미사 일치 정보"를 사전에 계산하여 사용합니다.

🔍 KMP의 핵심 아이디어

• 문자열 haystack에서 needle을 찾는 문제
• 부분 일치가 발생했을 때, 앞으로 돌아가지 않고 재사용할 수 있는 패턴을 저장
• 이때 사용하는 것이 LPS 배열 (Longest Prefix Suffix)

🧠 LPS 배열이란?

LPS(Longest Prefix Suffix) 배열은 자기 자신 내에서 접두사와 접미사가 일치하는 최대 길이를 저장하는 배열입니다.

예시: needle = "a b c d a b d"

index:   0 1 2 3 4 5 6
char:    a b c d a b d
LPS:     0 0 0 0 1 2 0

• LPS[5] = 2 → 앞에서 "ab"와 일치하는 접두사/접미사가 존재함

✅ KMP 알고리즘 구현 (TypeScript)

function computeLPS(pattern: string): number[] {
  const lps = new Array(pattern.length).fill(0);
  let length = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else {
      if (length !== 0) {
        length = lps[length - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps;
}

export function kmpSearch(haystack: string, needle: string): number {
  if (needle === "") return 0;

  const lps = computeLPS(needle);
  let i = 0; // haystack pointer
  let j = 0; // needle pointer

  while (i < haystack.length) {
    if (haystack[i] === needle[j]) {
      i++;
      j++;
    }

    if (j === needle.length) {
      return i - j;
    } else if (i < haystack.length && haystack[i] !== needle[j]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }

  return -1;
}

📈 시간 및 공간 복잡도

항목 복잡도 설명

✅ KMP의 장점

• 모든 케이스에서 최악의 경우에도 선형 시간 보장
• needle이 반복되는 경우에 유리함
• 보안, 컴파일러, 문자열 매칭 시스템에서 자주 사용됨

📌 문제 설명

문자열 haystack에서 부분 문자열 needle이 처음으로 등장하는 인덱스를 찾아 반환하는 문제입니다.

🔹 문제 해석

주어진 두 문자열 needle과 haystack이 있을 때, haystack에서 needle이 처음으로 등장하는 인덱스를 반환하라. 만약 존재하지 않으면 -1을 반환하라.

🔹 예시

Input: haystack = "sadbutsad", needle = "sad"
Output: 0

Input: haystack = "leetcode", needle = "leeto"
Output: -1

🔹 단어 정리

단어 의미

✅ 풀이 아이디어

• 부분 문자열 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;
}

✅ 시간 및 공간 복잡도

항목 복잡도

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