LeetCode 솔루션 분류
[7/20] 792. Number of Matching Subsequences
본문
Medium
3270158Add to ListShareGiven 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.
- 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 * 1041 <= words.length <= 50001 <= words[i].length <= 50sandwords[i]consist of only lowercase English letters.
Accepted
143,814
Submissions
282,523
태그
#Google
관련자료
-
링크
댓글 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.
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
