[LeetCode 75] Easy - 392. Is Subsequence

392. Is Subsequence

 

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 <= 10^4
• s and t consist only of lowercase English letters.

 

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 10^9, 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의 부분 문자열(subsequence)**인지 확인하는 것입니다.
**부분 문자열(subsequence)**은 문자열에서 일부 문자를 삭제(순서는 유지)하여 얻을 수 있는 새로운 문자열을 의미합니다.
예를 들어:

• "ace"는 "abcde"의 부분 문자열 → 문자 "a", "c", "e"를 순서대로 유지하며 추출 가능.
• "aec"는 "abcde"의 부분 문자열이 아님 → "c"와 "e"의 순서가 뒤바뀜.

---

문제 조건

1. 입력:
   • 문자열 s: 부분 문자열인지 확인할 문자열 (0 ≤ s.length ≤ 100).
   • 문자열 t: 대상 문자열 (0≤ t.length ≤ 10^4).
2. 출력:
   • True: s가 t의 부분 문자열인 경우.
   • False: 아닌 경우.
3. 추가 조건 (Follow-up):
   • s가 매우 많이 주어질 경우(k ≥ 10^9), 효율적으로 처리할 방법이 필요.

 

내 풀이

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s) == 0:  # 빈 문자열은 항상 부분 문자열
            return True

        s_idx = 0  # s의 현재 위치를 추적

        # t를 순회하며 s의 문자를 찾음
        for char in t:
            if s[s_idx] == char:
                s_idx += 1
                if s_idx == len(s):  # 모든 문자를 찾으면 True
                    return True

        # t를 끝까지 확인했지만 s를 모두 매칭하지 못한 경우
        return s_idx == len(s)

 

시간 복잡도

1. 루프:
   • 문자열 t를 한 번 순회하며 문자를 확인 → O(m), m=len(t).
   • 내부적으로 s_idx를 len(s)까지 증가시키며 s의 문자를 확인 → 최대 O(n), n=len(s).
2. 전체:
   • 루프의 모든 작업은 O(m) 이며, s의 길이만큼의 비교는 O(n) 입니다.
   • 최종 시간 복잡도: O(n+m).

---

공간 복잡도

1. 추가 공간 사용 여부:
   • 문자열 s와 t는 입력으로 주어진 그대로 사용합니다.
   • 추가적으로 사용하는 변수:
     • s_idx (정수): O(1).
     • char (문자): O(1).
2. 전체:
   • 입력 문자열 외에 추가 메모리를 사용하지 않음.
   • 최종 공간 복잡도: O(1).

---

요약

• 시간 복잡도: O(n+m), s와 t의 길이에 비례.
• 공간 복잡도: O(1), 추가 메모리 사용 없음.

최종 코드의 효율성은 매우 높으며, 입력 크기가 커져도 확장성이 좋습니다.

 

추가 참고 자료

 

https://youtu.be/99RVfqklbCE?si=1fWs9zO_hn0ehkcc

 

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

 

내 코드(3번째)

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if not len(s):
            return True

        s_l = 0
        t_l, t_r = 0, len(t)-1

        while t_l <= t_r and s_l < len(s):
            if t[t_l] == s[s_l]:
                s_l +=1
            t_l +=1
        return s_l == len(s)

 

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        s_l, t_l = 0, 0

        while s_l <len(s) and t_l <len(t):
            if s[s_l] == t[t_l]:
                s_l +=1
            t_l +=1
        
        return s_l == len(s)