792. Number of Matching Subsequences

// 792. Number of Matching Subsequences
// Runtime: 102 ms, faster than 45.36% of Java online submissions for Number of Matching Subsequences.
// Memory Usage: 42.4 MB, less than 59.13% of Java online submissions for Number of Matching Subsequences.



class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        //naive approach , iterate each word's letters over string's letters
        //2nd aprach
        // s = "abcde", words = ["a","bb","acd","ace"]
        //     a->  a, acd, ace
        //     b->  bb
        //     c-> 
        //     d-> 
        //     e-> 
        
        Map<Character , Queue<String>> map= new HashMap<>();
        int countOfMatch=0;
        
        
        for(int i=0;i<s.length();i++)
            map.putIfAbsent(s.charAt(i), new LinkedList<>());
        
        for(String word:words){
            char startingChar=word.charAt(0);
            if(map.containsKey(startingChar))
                map.get(startingChar).offer(word);
        }

        for(int i=0;i<s.length();i++){
            char startingChar=s.charAt(i);
            Queue<String> extractedList=map.get(startingChar);
            
            int size=extractedList.size();
                for(int k=0;k<size;k++){
                    String str=extractedList.poll();
                    
                        if(str.substring(1).length()==0)
                            countOfMatch++;
                        else if(map.containsKey(str.charAt(1)))
                            map.get(str.charAt(1)).add(str.substring(1));
                }
            
        }
        
        
        return countOfMatch;
    }
}