[Leetcode]792. Number of Matching Subsequences(x)

1. problem : 

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

 

2. solution 1 : 

from collections import defaultdict
from typing import List, Iterator

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        # defaultdict 초기화: 각 문자가 현재 기다리는 단어들을 저장
        waiting = defaultdict(list)
        
        # 각 단어의 첫 문자를 키로 하고, 나머지 문자의 이터레이터를 값으로 설정
        for word in words:
            waiting[word[0]].append(iter(word[1:]))
        
        # subsequence 매칭 카운터 초기화
        count = 0
        
        # 문자열 s를 순회하면서
        for char in s:
            # 현재 문자를 기다리는 단어들을 가져옴
            current_waiting = waiting[char]
            waiting[char] = []
            
            # 각 단어의 다음 문자를 업데이트
            for it in current_waiting:
                nxt = next(it, None)
                if nxt:
                    waiting[nxt].append(it)
                else:
                    count += 1
        
        return count

# 예제 문자열
s = "abc"
words = ["ab", "bcd"]

# 솔루션 인스턴스 생성 및 결과 출력
sol = Solution()
print(sol.numMatchingSubseq(s, words))  # Output: 1

이 문제는 내가 two-pointer로 풀었을 때 time limit이 걸려서, 실패했다. 그래서 chat gpt 4o한테 받은 코드다. 

1. defaultdict을 만든다. 이때, value는 iter를 이용해서, 반복가능한 형태로 만들어준다. 

2. 여기다가 앞머리를 키로 나머지를 value로 해준다. 단, value는 iteratable 한 형태다. 

3. 이제 s에서 char를 뽑아서, char인 key에 들어가 value들의 next()를 key로 그리고 나머지들을 또 value로 설정해 준다. 

4. 만약에 key가 없다고 나온다면, 그건 count += 1을 시켜준다. 왜냐하면, s라는 친구 안에 포함된다는 이야기이기 때문이다. 

 

풀이를 외우자.

 

3. solution 2 :

#%%
from collections import deque 
from collections import defaultdict 
from typing import List 
class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        waiting = defaultdict(deque)
        count = 0 
        for word in words:
            waiting[word[0]].append(word) 
        for char in s:
            current_waiting = waiting[char] 
            waiting[char] = deque()
            
            while current_waiting:
                word = current_waiting.popleft()
                if len(word) > 1:
                    waiting[word[1:]].append(word[1:])
                else:
                    count += 1 
        return count

이건 첫 번째 풀이와 똑같다. 다른 점은 deque를 이용한다는 점이다. deque는 stack과 queue를 합친 구조다. 선입선출도 가능하고 , 후입선출도 가능하다. list보다 훨씬 자유도가 높다. 

 

4. solution 3 :

from collections import defaultdict
from bisect import bisect_left
from typing import List

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        #1. Making dictionary(list) of s --> key : char,value : index of char
        pos = defaultdict(list)
        for i,char in enumerate(s):
            pos[char].append(i) 
        
        #2. Making function of compare index 
        def is_subsequence(word):
            current_pos = -1 
            for char in word:
                if char not in pos:
                    return False 
                char_pos = pos[char]
                idx = bisect_left(char_pos,current_pos+1)
                if idx == len(char_pos):
                    return False
                current_pos = char_pos[idx] 
            return True 
        
        count = sum(is_subsequence(word) for word in words)
        return count

이 풀이법은 복잡하다. 일단, 위의 풀이들과는 다르게 , s라는 string의 index를 활용해서 dictionary를 생성한다. 

def is_subsequence(word)는 word가 들어갔을 때, true or false를 반환해 주는 함수다. 

자세히 설명해 보자면, word의 각각의 char가 pos에 들어있지 않다면 false를 반환한다. 

그게 아니라면, bisect_left를 이용해서, current_pos + 1 이 char의 index의 어디에 들어가느냐를 확인한다. 만약 0이라면 current_pos+1보다 index가 크거나 같은 것이고, 1이라면, current_pos+1보다 index가 작다는 것이 된다. 만약에 1이 된다면, index가 current_pos+1의 앞쪽에 있다는 것을 알 수 있다. 따라서, index의 순서가 무너져, return false를 실행한다. 

그게 아니라면 return true를 반환한다.