Sponsored
Sponsored
Brute Force Approach: In this approach, for each word in the words array, we will check whether it is a subsequence of the string s or not. This is achieved by iterating over the characters of the word and trying to match them sequentially in the string s.
Time Complexity: O(n * m), where n is the length of the string s and m is the average length of the words. Space Complexity: O(1) since it only uses constant extra space.
1function isSubsequence(s, word) {
2 let i = 0, j = 0;
3 while (i < s.length && j < word.length) {
4 if (s[i] === word[j]) {
5 j++;
6 }
7 i++;
8 }
9 return j === word.length;
10}
11
12function numMatchingSubseq(s, words) {
13 let count = 0;
14 for (const word of words) {
15 if (isSubsequence(s, word)) {
16 count++;
17 }
18 }
19 return count;
20}The JavaScript solution defines an isSubsequence function that checks if a word is subsequence using a straightforward iteration method. numMatchingSubseq loops through each word to perform the check.
Efficient Group Matching: Group words by their initial characters in a dictionary and iterate over the string s to manage these groups of words, repositioning them towards completion as their current character is matched. This avoids re-checking each word from the beginning every time.
Time Complexity: O(n + m), where n is the length of s and m is the total number of characters across all words. Space Complexity: O(m) due to storage of iterators.
1import java.util.*;
2
3In the Java implementation, a hash map contains queues of character iterators. As we process each character in s, iterators corresponding to matching characters are advanced, effectively tracking sub-part integration progress.