[LeetCode 392] Is Subsequence - 부분 수열 판별하기

🔗 문제 링크: 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);
  });
});

---

📈 시간 및 공간 복잡도

항목 복잡도

시간	O(N) (t의 길이만큼)
공간	O(1) (추가 메모리 거의 없음)

---

✅ 마무리 정리

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