[Dart] 392. Is Subsequence

1. 문제

https://leetcode.com/problems/is-subsequence/description/?envType=study-plan-v2&envId=leetcode-75

 

 

2. 요구사항

1) 두 문자열 s와 t가 주어진다.

2) s가 t의 부분 수열이라면 true를 반환하고, 그렇지 않으면 false를 반환한다.

3) 부분 수열은 원래 문자의 순서를 유지하면서, 일부 문자를 삭제해서 얻을 수 있는 문자열이다.

4) 문자를 삭제할 수 있지만, 순서를 바꾸면 안된다.

 

 

 

3. 핵심 아이디어

1) 투 포인터

 

문자열 s와 t의 인덱스를 저장하는 sIdx와 tIdx를 사용하여

s의 현재 문자와 t의 현재 문자가 일치하는 문자가 발견되면 sIdx를 증가시킨다.

 

t를 끝까지 순회하는 동안 s의 모든 문자가 순서대로 나타난다면 sIdx 가 s.length와 값이 같아져 true를 반환한다.

 

 

2) 코드

bool isSubsequence(String s, String t) {
  int sIndex = 0; // s 문자열에서 비교할 현재 인덱스
  int tIndex = 0; // t 문자열에서 비교할 현재 인덱스

  // 두 문자열을 동시에 순회하면서,
  // s의 문자들이 t에서 순서대로 등장하는지 확인
  while (sIndex < s.length && tIndex < t.length) {
    // 현재 문자가 일치하면 s의 다음 문자로 이동
    if (s[sIndex] == t[tIndex]) {
      sIndex++;
    }
    // 항상 t는 다음 문자로 이동
    tIndex++;
  }

  // s의 모든 문자를 순서대로 찾은 경우 (부분 수열임)
  return sIndex == s.length;
}

 

- 시간 복잡도 : O(n)

- 공간 복잡도 : O(1)