[리트코드/leetcode/python] 392. Is Subsequence

이미지를 누르면 문제 링크를 보실 수 있습니다.

이 문제는 주어진 문자열 t 안에 s문자열이 있는지 아닌지를 판단하는 문제입니다.

예를 들어서, t가 ahbgdc 이고, s가 abc 라면, ahbgdc에서 h,g,d,를 제거하면 abc가 되므로 true를 반환합니다.

반면, 만약 t가 abcde이고, s가 aec 라면, abcde 문자열에서 어떤 수를 써서라도 aec를 만들 수 없기에 false를 반환합니다.

즉, t의 원래의 문자열에서 순서는 유지한 채 수열을 이루는 항 중에 일부만 모아 s가 만들어진다면, true를 반환하고, 그렇지 않다면 false를 반환하면 됩니다.

 

코드를 통해 살펴보죠.

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

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

저는 idx를 0으로 초기화하고 cnt라는 변수를 통해 t에 s의 문자열이 포함될 때마다 증가시키는 로직을 짰습니다.

s의 길이가 "" 와 같이 0이라면 당연히 답은 True를 반환하고

s가 길이가 0이 아니라면, s를 처음부터 비교하며 t를 순회합니다. subSequence인지 아닌지를 판단하는 것이기 때문에 순서도 같아야 하므로 처음부터 끝까지 비교하면 되는것이죠.

 

이 때, len(s) == cnt 라는 비교 분기문을 넣어준 이유는 idx가 1 증가했는데, 문자열 s에서 더이상 바라볼 문자가 없다면, 인덱스 오류가 나기 때문에 바로 for문을 탈출하는 작업을 넣어줬습니다.

예를 들어, 문자열 s가 "b" 이고 문자열 t가 "acbed" 라면 t를 돌면서 b를 가리키는 순간 idx는 1증가하고 cnt도 1증가하게 됩니다. 이 때, if len(s) == cnt 문이 없다면, e를 가리키는 순간 s[1]을 하기 때문에 인덱스 오류가 나는 것을 방지하지 못합니다.

따라서, 더 이상 바라볼 문자가 없다면, 바로 for문을 탈출하는 셈이죠.

 

for문을 빠져나왔다면, cnt와 s의 길이를 비교해서 같다면, true를 반환하고, 그렇지 못하다면, false를 반환하면 됩니다.

 

이상 Is Subsequence 문제를 정리해봤습니다.