[파이썬/LeetCode 792]Number of Matching Subsequences

링크 https://leetcode.com/problems/number-of-matching-subsequences/

Number of Matching Subsequences - LeetCode

문제

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

 

코드

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        
        def isSubseq(s: str, word: str) -> bool:
            stack = list(word)
            n = len(s)
            for i in range(n-1, -1, -1):
                if not stack:
                    return True
                if stack[-1] == s[i]:
                    stack.pop()
            return stack == []        
        
        answer = 0
        cache = dict()
        for word in words:
            if word not in cache:
                cache[word] = isSubseq(s, word)
            answer += cache[word]

        return answer 

딕셔너리 cache에 이미 부분문자열인지 확인한 결과를 저장해두지 않으면 TLE가 발생하니 주의해야 한다. 문제의 조건에 words 리스트에 중복이 없다는 말이 없기 때문이다.

 

글을 쓰면서 생각해보니 굳이 stack을 쓸 필요도 없이 인덱스로만 풀어도 될 것 같다. 굳이 list로 만들지도 않고, 제거하는 작업도 없으니 더 효율적일 것 같다.

 

그리고 leetcode discuss(링크) 에 엄청 효율적인 풀이가 올라와있다.

Efficient and simple, go through words in parallel, with explanation - LeetCode Discuss

이터레이터를 사용한 풀이인데, 간결하고 깔끔하게 풀려있다. 이터레이터를 적재적소에 사용하면 풀이 시간이 상당히 빨라지는 만큼 이 풀이도 효율적인데, 내가 사용해보지 않은 문법이라서 그런지 한번에 딱 이해되지는 않는다.

 

추가 공부가 필요할 것 같다.