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.
1#include <stdbool.h>
2#include <string.h>
3
4bool isSubsequence(char* s, char* word) {
5 int i = 0, j = 0;
6 while (i < strlen(s) && j < strlen(word)) {
7 if (s[i] == word[j]) {
8 j++;
9 }
10 i++;
11 }
12 return j == strlen(word);
13}
14
15int numMatchingSubseq(char* s, char** words, int wordsSize) {
16 int count = 0;
17 for (int i = 0; i < wordsSize; i++) {
18 if (isSubsequence(s, words[i])) {
19 count++;
20 }
21 }
22 return count;
23}This implementation involves a helper function isSubsequence that checks if a given word is a subsequence of the string s. We iterate through each word in the array and utilize the helper function to accumulate the count of matching subsequences.
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.
1from collections import defaultdict
2
3def In this Python approach, we store word iterators in a dictionary waiting, initially keyed by their starting character. As we advance through s, we update the waiting list for each character to track partially matched words, dramatically improving efficiency.