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.
1def is_subsequence(s, word):
2 it = iter(s)
3 return all(char in it for char in word)
4
5class Solution:
6 def numMatchingSubseq(self, s: str, words: List[str]) -> int:
7 count = 0
8 for word in words:
9 if is_subsequence(s, word):
10 count += 1
11 return countIn the Python implementation, a helper function is_subsequence uses an iterator to determine if the word is a subsequence of the string s. This method leverages Python's expressive iteration features for a concise result.
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.