[Leetcode] 392. Is Subsequence 해설 및 풀이 (Python)

 

LeetCode 392. Is Subsequence

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

 

---

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

 

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false
 

Constraints:

0 <= s.length <= 100
0 <= t.length <= 104
s and t consist only of lowercase English letters.
 

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

 

한글 해석

 

두 문자열 s과 가 주어졌을 때 t, 가 의 하위 시퀀스true 이면 를 s반환 하고 t, false그렇지 않으면 를 반환합니다 .

문자열의 하위 시퀀스 는 원래 문자열에서 일부 문자(전혀 없을 수도 있음)를 삭제하여 나머지 문자의 상대적 위치를 변경하지 않고 형성된 새로운 문자열입니다. (즉, is는 while is not "ace"의 하위 시퀀스입니다 .)"abcde""aec"

 

예시 1:

입력: s = "abc", t = "ahbgdc"
 출력: true
예 2:

입력: s = "axc", t = "ahbgdc"
 출력: false
 

제약 조건:

0 <= s.length <= 100
0 <= t.length <= 104
s소문자 t영어 문자로만 구성됩니다.
 

추가 질문: 에서 처럼 많은 가 수신되고, 가 하위 시퀀스를 가지고 있는지 하나씩 확인하고 싶다고 가정 s해 보겠습니다 . 이 경우 코드를 어떻게 변경해야 할까요?s1, s2, ..., skk >= 109t

 

---

문제 유형

Two Pointers

String

Dynamic Programming

 

풀이 방법 도출

 

문자열 s가 문자열 t의 subsequence인지 확인하려면 s의 문자들이 t에 순서대로 존재하는지를 확인해야 합니다.

예를 들어 s = "abc"이고 t = "ahbgdc"인 경우, s의 첫 글자 'a'는 t에서 처음 등장합니다. 다음 글자 'b'도 그 이후에 등장합니다. 'c'도 그 이후에 등장합니다.

 

순서를 지키며 t 내에서 s의 각 문자를 찾을 수 있으므로 True를 반환합니다.

 

이때 s 문자열을 따라가는 인덱스 s_index와 t 문자열을 따라가는 인덱스 t_index를 투 포인터로 사용합니다.

t_index를 이동시키며 s[s_index] == t[t_index]이면 s_index도 하나 증가시키고,

마지막에 s_index == len(s)이면 subsequence입니다.

 

 

시간 복잡도

• O(N)

---

핵심 코드 삽입 및 설명

 

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if not s:
            return True
        if not t:
            return False
        
        s_index = 0
        t_index = 0
        
        while s_index < len(s) and t_index < len(t):
            if s[s_index] == t[t_index]:
                s_index += 1
            t_index += 1
        
        return s_index == len(s)