Press "Enter" to skip to content

花花酱 LeetCode 792. Number of Matching Subsequences

题目大意:给你一些单词,问有多少单词出现在字符串S的子序列中。

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.

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

Solution 1: Brute Force

Time complexity: O((S + L) * W)

C++ w/o cache TLE

Space complexity: O(1)

C++ w/ cache 155 ms

Space complexity: O(W * L)

Solution 2: Indexing+ Binary Search

Time complexity: O(S + W * L * log(S))

Space complexity: O(S)

S: length of S

W: number of words

L: length of a word

C++

Java

 

Python 3:

w/o cache

w/ cache

 

请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物(任意商品)来支持我们

Paypal
Venmo
huahualeetcode
微信打赏

Be First to Comment

Leave a Reply