792-number-of-matching-subsequences

Try it on leetcode

Description

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.

Solution(Python)

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        return self.optimal(s, words)

    # Time Complexity: O(n*m)
    # space complexity: O(1)
    def naive(self, s: str, words: List[str]) -> int:
        cnt = 0

        def issubsequence(s, word):
            i = 0
            if len(word) > len(s):
                return False
            for c in s:
                if i < len(word) and word[i] == c:
                    i += 1
            return i == len(word)

        for word in words:
            if issubsequence(s, word):
                cnt += 1
        return cnt

    # Time Complexity: O(n*m)
    # space complexity: O(n)
    def better(self, s: str, words: List[str]) -> int:
        def issubseq(s, t):
            stack = []
            for i in t:
                stack.append(i)

            n = len(s)
            for i in range(n - 1, -1, -1):
                if not stack:
                    return True
                if stack[-1] == s[i]:
                    stack.pop()
            return stack == []

        hashmap = {}

        count = 0
        for word in words:
            if word not in hashmap:
                if issubseq(s, word):
                    count += 1
                    hashmap[word] = True
                else:
                    hashmap[word] = False
            else:
                if hashmap[word]:
                    count += 1
        return count

    # Time Complexity: O(nlogm)
    # space complexity: O(n)
    def optimal(self, s: str, words: List[str]) -> int:
        def issubseq(t):
            current_pos = -1
            stack = []
            for i in t:
                if indices[i]:
                    pos = bisect.bisect_right(indices[i], current_pos)
                    if pos == len(indices[i]):
                        return False
                    current_pos = indices[i][pos]
                else:
                    return False
            return True

        indices = defaultdict(list)
        for i, c in enumerate(s):
            indices[c].append(i)

        hashmap = {}

        count = 0
        for word in words:
            if word not in hashmap:
                if issubseq(word):
                    count += 1
                    hashmap[word] = True
                else:
                    hashmap[word] = False
            else:
                if hashmap[word]:
                    count += 1
        return count