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.
1public class Solution {
2 public boolean isSubsequence(String s, String word) {
3 int i = 0, j = 0;
4 while (i < s.length() && j < word.length()) {
5 if (s.charAt(i) == word.charAt(j)) {
6 j++;
7 }
8 i++;
9 }
10 return j == word.length();
11 }
12
13 public int numMatchingSubseq(String s, String[] words) {
14 int count = 0;
15 for (String word : words) {
16 if (isSubsequence(s, word)) {
17 count++;
18 }
19 }
20 return count;
21 }
22}In the Java solution, the main method iterates over each word to determine if it is a subsequence of the string s using a helper method isSubsequence. This inline check for each character ensures correctness.
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.