엔지니어 게시판
LeetCode 솔루션 분류

[7/20] 792. Number of Matching Subsequences

작성자 정보

  • 학부유학생 작성
  • 작성일

컨텐츠 정보

본문

Medium
3270158Add to ListShare

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

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.

  • For example, "ace" is a subsequence of "abcde".

 

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

 

Constraints:

  • 1 <= s.length <= 5 * 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 50
  • s and words[i] consist of only lowercase English letters.
Accepted
143,814
Submissions
282,523
태그

관련자료

댓글 1

학부유학생님의 댓글

  • 학부유학생
  • 작성일
Runtime: 422 ms, faster than 91.49% of Python3 online submissions for Number of Matching Subsequences.
Memory Usage: 15.6 MB, less than 75.71% of Python3 online submissions for Number of Matching Subsequences.
from collections import defaultdict
class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        word_dict = defaultdict(list)
        count = 0
        
        for word in words:
            word_dict[word[0]].append(word)
        
        for char in s:
            
            temp = word_dict[char]
            word_dict[char] = []
            
            for subseq in temp:
                if len(subseq) == 1:
                    count += 1
                else:
                    word_dict[subseq[1]].append(subseq[1:])
                    
        return count
전체 240 / 1 페이지
게시글 쓰기
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 63 명
  • 오늘 방문자 787 명
  • 어제 방문자 1,117 명
  • 최대 방문자 1,463 명
  • 전체 회원수 378 명
알림 0