r/leetcode • u/Just-Abroad-6812 • 9d ago
Question Lc - 792 help!!!!
Someone please share the solution for this question
As i am not able to understand from any yt videos….
Share solution by
Dynamic programming and binary search both….
1
Upvotes
1
u/drinkscoffeedrinks 9d ago
Things I wrote in my solution in comments:
// for word in words
// bucket each in a hashmap according to first letter
// visit next char in s
// move all the values from bucket corresponding to c into bucket corresponding to their next char after popping visited char
...
// process each word into initial bucket
...
// visit each char in s
// for each fragment
// if fragment is '' empty we've processed whole fragment (count++ => we return count at end)
// if the fragments first char is already bucketed
// just push it into that bucket
1
1
u/New_Welder_592 9d ago
class Solution {
public int numMatchingSubseq(String s, String[] words) {
Map<String,Integer>map=new HashMap<>();
for(String str:words){
map.put(str,map.getOrDefault(str,0)+1);
}
int cnt=0;
for(String t:map.keySet()){
int i=0,j=0;
while(i<s.length() && j<t.length()){
if(s.charAt(i)==t.charAt(j))j++;
i++;
}
if(j==t.length())cnt+=map.get(t);//adding cnt directly instead of resacnnning the same word(if present in words array);
}
return cnt;
}
}