알고리즘/Problem Solving

LeetCode - 392. Is Subsequence

도툐리 2023. 3. 20. 01:03

https://leetcode.com/problems/is-subsequence/?envType=study-plan&id=level-1 

 

Is Subsequence - LeetCode

Can you solve this real interview question? 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 n

leetcode.com

내 잘못된 첫 풀이

아.. 빈 string일 경우를 생각을 못함

 

 

다시 고친 내 두번째 풀이

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        s_len = len(s)
        t_len = len(t)
        if s_len > t_len:
            return False
        if s_len==0:
            return True
        
        # ptr : s의 char을 idx 차례로 훑는 pointer
        ptr = 0
        for i in range(t_len):
            if s[ptr]==t[i]:
                ptr+=1
                if ptr==s_len:
                    return True
        return False

 

음.. 속도가 상위 39퍼 정도긴 한데 좀더 발전시킬 수 있는지 한번 봐볼까

 

속도 개선한 풀이

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        s_len = len(s)
        if s_len==0:
            return True
        t_len = len(t)
        if s_len > t_len:
            return False
        
        # ptr : s의 char을 idx 차례로 훑는 pointer
        ptr = 0
        for i in range(t_len):
            if s[ptr]==t[i]:
                ptr+=1
                if ptr==s_len:
                    return True
        return False

와우..

맨 위  if s_len==0:
            return True 부분

위치 재배치 했더니 갑자기 상위 0.5퍼 됨

 


-> 느낀점:

아주 사소한 부분일지라도 로직을 어디에 위치시키냐에 따라 속도가 확 개선될 수 있음