LeetCode / String /392번 / Is Subsequence / JS

< 문제 바로가기 >

Is Subsequence - LeetCode

 

< 문제 간단설명 >

문자열로 s와 t가 주어진다. 이때 주어진 s의 각각 문자가 s에서의 순서를 지키면서 t에 속하는지 판단하면 되는 문제이다.

 

예를들어 s = 'abc', t = 'ahbgdc' 와 같이 주어졌다고 해보자.

s에서는 a, b, c가 차례대로 있다. t에서도 마찬가지로 a, h, b, g, d, c 에서 s에 속하는 a, b, c만 보면 차례를 지키고있다.

이해가 안되면 다음과 같이 색깔로 나타내면 이해가 쉬울것이다.

 

s = a b c

t = a h b g d c

 

따라서 위의 예시는 s의 모든 알파벳이 t에서 그대로 차례를 지키고 있기 때문에 true를 반환해준다.

 

또 다른 예시인 s = 'axc', t = 'ahbgdc' 와 같이 주어졌다고 해보자.

s에서의 'a'와 'c'는 t에서도 똑같이 순서를 지키고 있지만, s에 존재하는 'x'가 t에 없기 때문에 false를 반환한다.

 

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
  if (s.length === 0) return true;
  if (s.length > t.length) return false;

  let [pointerS, pointerT] = [0, 0];
  while (true) {
    if (pointerS === s.length || pointerT === t.length) {
      break;
    }

    if (s.at(pointerS) === t.at(pointerT)) {
      pointerS += 1;
      pointerT += 1;
    } else {
      pointerT += 1;
    }
  }

  return pointerS === s.length;
};

---

먼저 최상단의 조건문부터 살펴보자.

사실 s가 빈 문자열일 경우는 생각을 못하고 있었는데 테스트케이스에서 보니 빈 문자열일 경우 무조건 true라서 추가해주었다.

그리고 s가 t보다 문자열의 길이가 더 길다면 t에 속할 수 없으므로 무조건 false를 반환해준다.

 

그 후에는 각각 s와 t의 맨 앞을 가리키는 pointer인 pointerS와 pointerT 를 선언해서 two-pointer 방식으로 풀어주었다.

반복문으로 순회를 하게되는데, pointerS가 s끝에 다다르거나, pointerT가 t의 끝에 다다르면 반복문을 중단한다.

그리고 s와 t의 각각의 포인터가 현재 가리키는 문자가 같다면 pointerS와 pointerT 모두 하나씩 증가시켜준다.

만약 다르다면, 현재 s의 문자와 t의 그 다음문자를 비교해봐야 하므로 pointerT만 하나 증가시켜준다.

 

이런 방식으로 만약 pointerS가 s의 끝에 다다랐다면 모든 문자가 T에 속해있다는 뜻이므로 true를 반환하게 된다.