0792._Number_of_Matching_Subsequences.md

792. Number of Matching Subsequences

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/number-of-matching-subsequences/description/

内容描述

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

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

All words in words and S will only consists of lowercase letters.
The length of S will be in the range of [1, 50000].
The length of words will be in the range of [1, 5000].
The length of words[i] will be in the range of [1, 50].

解题方案

假设words里面最长的word长度为m，words的长度为n，S的长度为s

思路 1 - 时间复杂度: O(mns)- 空间复杂度: O(1)****

暴力，超时

class Solution(object):
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        def match(word, S):
            i, j = 0, 0
            while i < len(word) and j < len(S):
                if word[i] == S[j]:
                    i += 1
                    j += 1
                else:
                    j += 1
            return i == len(word)
        
        res = 0
        for word in words:
            if match(word, S):
                res += 1
        return res

我觉得是不是多加一个判断，如果一个字符在S里面没有立马返回False这样会快一点，但是还是超时

class Solution(object):
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        def match(word, S):
            i = 0
            while S and i < len(word):
                idx = S.find(word[i])
                if idx == -1:
                    return False
                S = S[idx+1:]
                i += 1
            return i == len(word)
        
        res = 0
        for word in words:
            if match(word, S):
                res += 1
        return res

于是又觉得用自带的iter函数会不会快一点，结果还是超时

class Solution(object):
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        def match(word, S):
            it = iter(S)
            if all(c in it for c in word):
                return True
            return False
        
        res = 0
        for word in words:
            if match(word, S):
                res += 1
        return res

思路 2 - 时间复杂度: O(mns)- 空间复杂度: O(N)****

终于，我想到了用memorization，AC了，beats 70.4%

class Solution(object):
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        def match(word, S):
            it = iter(S)
            if all(c in it for c in word):
                return True
            return False
        
        res = 0
        matched, unmatched = set(), set()
        for word in words:
            if word in matched:
                res += 1
                continue
            elif word in unmatched:
                continue
            else:
                if match(word, S):
                    res += 1
                    matched.add(word)
                else:
                    unmatched.add(word)
        return res

然后换了之前我觉得写的最好最快的match函数，beats 100%

class Solution(object):
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        def match(sub, s):
            idx = 0
            for c in sub:
                idx = s.find(c, idx) + 1
                if idx == 0:
                    return False
            return True
        
        res = 0
        matched, unmatched = set(), set()
        for word in words:
            if word in matched:
                res += 1
                continue
            elif word in unmatched:
                continue
            else:
                if match(word, S):
                    res += 1
                    matched.add(word)
                else:
                    unmatched.add(word)
        return res