리트코드 - 392. Is Subsequence

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

Is Subsequence - LeetCode

두 문자열 s와 t가 주어지면, s가 t의 후속이면 True을 반환하고, 그렇지 않으면 False을 반환한다.

 

두 개의 인덱스 위치 변수를 만들고 순회를 진행하면서 일치할 경우 이동시키면서 후속 문자열의 여부를 확인하였다.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        sp_1, sp_2 = 0, 0 # O(1)

        while sp_1 < len(s) and sp_2 < len(t): # O(n) n은 t의 길이
            if s[sp_1] == t[sp_2]: # O(1)
                sp_1 += 1 # O(1)
            sp_2 += 1 # O(1)
        
        if sp_1 == len(s): # O(1)
            return True
        
        return False

 

종합적으로, 이 코드의 시간 복잡도는 O(n)이고, 입력된 문자열 외에는 추가적인 정수 변수만 활용하므로 공간 복잡도는 O(1)이다.