leetcode/ 392. Is Subsequence

Description

Is Subsequence - LeetCode

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).

---

Process

Constraints:

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• s and t consist only of lowercase English letters.

문자열 t에서 문자열 s의 요소들이 순서대로 나타나는지 확인하는 문제다.

처음엔 정규식으로 s를 제외한 문자들을 다 제거하고 set으로 중복을 제거하고 s와 비교해볼까? 했지만 순서가 보장되어야 한다. 이럴 바엔 그냥 반복문 돌리면서 찾는 게 낫겠다는 생각을 했다. t의 범위는 안전권이지만 더 좋은 방법이 있지 않을까! 하고 한참 고민했지만 떠올리지 못했고 제출한 코드는 통과는 했지만 무려 타임 퍼센트가................................

---

Solution1: Time: 41 ms (15.29%), Space: 13.9 MB (30.89%)

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s) == 0:
            return True
        idx = 0
        for tt in t:
            if tt == s[idx]:
                idx += 1
            if idx == len(s):
                return True
        return False

1. s의 길이가 0인 경우 바로 True를 반환해준다

2. 문자열 s의 확인할 인덱스를 0으로 초기화 해준다

3. 문자열 t를 순회한다

4. 비교할 문자(s[idx])를 문자열 t 안에서 찾았다면 비교할 문자의 위치를 한칸 옮겨준다

5. s의 문자를 t에서 다 찾았다면 True를 반환한다

6. t 순회 후는 찾지 못한 경우이므로 False를 반환한다

 

---

Solution2: Time: 33 ms (64.75%), Space: 14 MB (8.37%)

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s) == 0:
            return True
        if len(s) > len(t):
            return False
        idx = 0
        for tt in t:
            if tt == s[idx]:
                idx += 1
            if idx == len(s):
                return True
        return False

코드 구조는 위와 같고 단지 문자열 t를 순회하기 전에 문자열 s의 길이가 t보다 큰 경우 s를 t에서 절대 찾을 수 없으므로 바로 False를 반환하는 분기가 추가되었다. 단 하나의 분기 추가로 성능 차이가 꽤 난다. 

---

Conclusion

여전히 예외를 고려하지 못한다. 테스트 케이스 다 걸리고 나서야 길이를 확인해보고요? (can be none) of the characters 이라고 친절하게 명시까지 해줬는데 설계할 때 전혀 고려하지 않았다.

추가로, 수행할 필요가 없는 경우는 미리 처리해주는 게 성능에서 이점을 본다는 것 역시 고려하지 않았다. 결과는 같겠지만 불필요한 과정이 수행된다면 제거할 것을 염두하자.

다음엔 잘하자. 얍