⭐️ LeetCode 알고리즘 풀이 (with Python)

# Is Subsequence

[Quetion]

LeetCode 392. Is Subsequence

📌 접근법

[문제 이해]

• t 문자열에서 특정 문자를 제거한 하위 문자열 s가 맞으면 True

처음에는 s문자열이 단순히 t문자열에 있으면 True가 된다고 판단하여 코드를 구현했다.

# 실패한 시도
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # t 안에 s가 있는지 확인
        for i in s:
            if i not in t:
                return False
        return True 

하지만 단순히 있는지 확인하는 것이 아니라 s문자열의 순서에 맞게 t문자열에 포함되어야 했다.
그래서 실패한 시도에 더하여 s문자열이 t문자열에 있으면 t에서 그 문자열의 인덱스까지 슬라이싱하는 방법으로 접근했다.

💻 구현

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        for i in s:
            if i not in t:
                return False
            if i in t:
                t = t[t.index(i)+1:]
        return True

Runtime: 42ms | Memory: 16.3MB
LeetCode 코드 중 Runtime 53%, Memory 88% 해당하는 결과

📝 Is Subsequence 회고

• 구현한 코드의 시간 복잡도는 O(s * t)이므로 O(n)의 시간복잡도 보다 느리다.
• in 연산자도 O(n)의 시간복잡도를 가지고, index() 함수도 O(n)의 시간복잡도가 걸리기 때문이다.
• 그래서 포인터를 for문 내부의 포인터와 s를 가르키는 포인터 2개를 활용하는 투포인터 접근법으로 다시 개선했다.

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

        for i in t:
            if len(s) <= pointer:
                break
            if s[pointer] == i:
                pointer += 1
        
        if len(s) == pointer:
            return True
        else:
            return False

Runtime: 42ms ---> 28ms
Memory: 16.3MB ---> 16.4MB

• 가장 처음 s가 ""일 경우, 모든 t에 포함되므로 True 반환
• s의 길이보다 포인터의 길이가 크면 반복문을 탈출 (index out of error 방지)
• 포인터가 가르키는 s문자열이 t문자열과 같으면 포인터가 s의 다음 문자열을 가르킴
• 만약 포인터의 길이와 s 문자열의 길이가 같다면 모두 포함된다는 의미라서 True

코드는 조금 더 복잡해졌지만, 투포인터 접근법을 활용하여 시간복잡도는 O(t)즉 O(n)으로 개선되었다.
그래서 leetcode 기준 98%의 Runtime으로 속도를 2배가량 개선하게 되었다.