Number of Matching Subsequences
Problem 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
sandwords[i]consist of only lowercase English letters.
Solve it on LeetCode
Approaches
1. Brute Force
The brute force approach involves checking if each word in the list of words is a subsequence of the string s by iterating over both the string and the word.
Intuition:
For each word, use two pointers to check if it's a subsequence of s. One pointer iterates over the string s and the other iterates over the current word. By using these pointers, we can check if all characters of the word appear in the same order in s.
Code:
- Time Complexity: O(n * m) where
nis the length of the stringsandmis the total length of all words combined. - Space Complexity: O(1), apart from input space.
2. HashMap
Instead of checking each word one by one, we can preprocess the string s to speed up the lookup of subsequence verification. We record the indices of each character in s, and for each word, we use this information to see if the characters appear in order.
Intuition:
Create a mapping from each character in s to the list of indices where that character occurs. For each word, check each character in order, using binary search to find a valid position for the next character.
Code:
- Time Complexity: O(n + m * log k) where
nis the length of the strings,mis the total length of all words combined, andkis the maximum length of indices lists. - Space Complexity: O(n) for storing index lists.
3. Binary Search
This approach involves using a binary search strategy to locate the next character of each word in s, optimizing the search for characters using a mapping similar to the Efficient Dictionary Approach.
Intuition:
For each word, leverage binary search to efficiently decide if the sequence of characters can be found in order by navigating the index list of each character in s.
Code:
- Time Complexity: O(n + m * log k), where
nis the length ofs,mis the total length of the words, andkis the length of the indices list for a character. - Space Complexity: O(n), due to storage of character indices.