392. Is Subsequence

Leetcode 392번 풀이

문제

Is Subsequence

풀이 1 (2025-08-12)

아이디어

s가 t의 subsequence인지 확인하는 문제다. s에 등장하는 문자 순서대로 t에 모두 등장하는지만 확인하면 된다. 투포인터를 이용해서 구현했다.

엣지 케이스인 둘 중 하나가 빈 문자열인 경우를 처리했다. s가 빈 문자열이면 항상 true를 반환하고, t가 빈 문자열이면 s가 빈 문자열이 아닌 이상 false를 반환한다.

코드

function isSubsequence(s: string, t: string): boolean {
  let sIdx = 0,
    tIdx = 0;
  if (s.length === 0) return true;
  if (t.length === 0) return false;
  while (sIdx < s.length && tIdx < t.length) {
    const sChar = s[sIdx];
    while (tIdx < t.length && t[tIdx] !== sChar) {
      tIdx++;
    }
    if (tIdx >= t.length) return false;
    tIdx++;
    sIdx++;
  }
  return sIdx === s.length;
}

시간 / 공간 복잡도

• 시간 복잡도: O(n) — t의 길이 n에 대해 한 번 순회
• 공간 복잡도: O(1)

풀이 2 (2026-03-30)

아이디어

풀이 1과 동일한 방법으로 풀었는데 코드가 좀 더 간결해졌다. s의 각 문자에 대해서 t에서 등장하는 위치를 찾는 방식으로 구현했다.

for…of 루프를 이용해서 s의 각 문자를 순회하면서, t에서 해당 문자가 등장하는 위치를 찾는다. 만약 t의 끝까지 탐색했는데도 해당 문자가 등장하지 않으면 false를 반환한다. 모든 문자가 순서대로 등장하면 true를 반환한다.

코드

function isSubsequence(s: string, t: string): boolean {
  // s가 t의 subsequence인지를 확인해야 함.
  // s에 등장하는 문자 순서대로 t에 모두 등장하는지만 확인하면 된다.
  let tidx = 0;
  for (const c of s) {
    while (tidx < t.length && c !== t[tidx]) tidx++;
    if (tidx >= t.length) return false;
    tidx++;
  }
  return true;
}

시간 / 공간 복잡도

• 시간 복잡도: O(n) — t의 길이 n에 대해 한 번 순회
• 공간 복잡도: O(1)