792. Number of Matching Subsequences

Medium (Trung bình) Python 🔗 Xem trên LeetCode

📋 Đề Bài

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.

  • 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.

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

Python 0792-number-of-matching-subsequences.py 
class Node:
    def __init__(self, word):
        self.word = word
        self.index = 0

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        buckets = defaultdict(list)
        
        for word in words:
            buckets[word[0]].append(Node(word))
            
        ans = 0
            
        for c in s:
            currBuckets = buckets[c]
            buckets[c] = []
            for node in currBuckets:
                node.index += 1
                if node.index == len(node.word):
                    ans += 1
                else:
                    buckets[node.word[node.index]].append(node)
                    
        return ans