Number of Matching Subsequences

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

Number of Matching Subsequences - LeetCode

문제 해설 : 문자열 s와 문자열 배열 words가 주어집니다. 이 때 s의 subsequence를 만족하는 words[i]의 개수를 반환하는 함수를 작성하세요. (subsequence는 기존 문자열에서 순서를 바꾸지 않고 character를 삭제해서 만들 수 있는 새로운 문자열을 말합니다. 예를 들어 "ace"는 "abced"의 subsequence 입니다.)

 

제한 사항

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters

 

문자열 리스트 words의 각 원소를 word라고 하면

각 word마다 s의 subsequence가 될 수 있는지 판별하는 함수를 작성해서 문제를 해결했습니다.

def isMatched(self, dic:dict, word:str) -> bool:
    idx = -1
    for ch in word:
        temp = bisect_right(dic[ch], idx)
        if temp == len(dic[ch]):
            return False
        idx = dic[ch][temp]
    return True

 

dic은 dictionary class로 a-z 모든 알파벳에 대하여 s 문자열 내 인덱스를 저장하는 list를 저장했습니다.

예를 들어, 문자열 s가 "dsahjpjauf"일 때 dic은 아래와 같습니다.

 

{'a': [2, 7], 'b': [], 'c': [], 'd': [0], 'e': [], 'f': [9], 'g': [], 'h': [3], 'i': [], 'j': [4, 6], 'k': [], 'l': [], 'm': [], 'n': [], 'o': [], 'p': [5], 'q': [], 'r': [], 's': [1], 't': [], 'u': [8], 'v': [], 'w': [], 'x': [], 'y': [], 'z': []}

 

dic 안에 저장된 list에서 현재 idx 이상이면서 가장 작은 인덱스를 고르는 것이 항상 최선의 방법이므로

이분탐색을 이용하여 idx보다 큰 값을 찾습니다.

만약 idx보다 큰 값이 list 내에 없다면(bisect_right의 결과값이 list의 길이와 같다면) 해당 character에 대해 선택 가능한 경우가 없음을 의미하므로 False를 반환합니다.

 

 

전체 코드는 아래와 같습니다.

from typing import List
import string
from bisect import bisect_right

class Solution:
    
    def isMatched(self, dic:dict, word:str) -> bool:
        idx = -1
        for ch in word:
            temp = bisect_right(dic[ch], idx)
            if temp == len(dic[ch]):
                return False
            idx = dic[ch][temp]
        return True

    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        alphabet_list = list(string.ascii_lowercase)
        dic = dict()
        for alphabet in alphabet_list:
            dic.update({alphabet:[]})
        
        for i in range(len(s)):
            ch = s[i]
            dic[ch].append(i)
        
        answer = 0
        for word in words:
            if self.isMatched(dic, word):
                answer += 1

        return answer