LC-0792 Medium LeetCode

792. Number of Matching Subsequences

Array Hash Table String Binary Search Dynamic Programming Trie Sorting

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 51% Topics: Array, Hash Table, String, Binary Search, Dynamic Programming, Trie, Sorting

Reading material

Arrays & Hashing 12 min Strings 12 min Binary Search 12 min

Reference solution (spoiler · python)

# Time:  O(n + w), n is the size of S, w is the size of words
# Space: O(k), k is the number of words

import collections


class Solution(object):
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        waiting = collections.defaultdict(list)
        for word in words:
            it = iter(word)
            waiting[next(it, None)].append(it)
        for c in S:
            for it in waiting.pop(c, ()):
                waiting[next(it, None)].append(it)
        return len(waiting[None])

Solution from kamyu104/LeetCode-Solutions · MIT