Python Solution With Detailed Explanation
Hello! Before I explain my solution, I would like to give credit to the post that inspired it. Here is a link with a description of the original algorithm.\n\nI
Hello! Before I explain my solution, I would like to give credit to the post that inspired it. [Here is a link](https://leetcode.com/problems/number-of-matching-subsequences/discuss/117634/Efficient-and-simple-go-through-words-in-parallel-with-explanation) with a description of the original algorithm.\n\nI begin by creating a default dictionary of \'list\' objects. The main benefit of a default dictionary is that when you access an entry that does not yet exist, the entry is created automatically (in this case, the value for the entry is an empty list when it is created). I then create a \'count\' variable to keep track of the number of words that are subsequences of the given string.\n\nThe first thing I do with the dictionary is populate it with all the words in the list of words. The key for each entry is the first letter of the word. The value is the list of words that start with that letter. Using the example in the problem, the dictionary would look like the following:\n\n{\'a\': [\'a\', \'acd\', \'ace\'], \'b\': [\'bb\']}\n\nThe next step is to iterate through each character in the given string. For each character, I access the dictionary to retrieve the list of words that start with that character. I reset the value of the entry to an empty list and then iterate through the list of words I retrieved. If the word is only a single letter, then I conclude that we have successfully found a completed subsequence and increase our \'count\' by one. Otherwise, I slice off the first character and add the sliced word back to the dictionary. This time, it is added to the entry for which the key is equal to the first letter of the sliced word.\n\nThis process continues until we have iterated through all characters in the string. At the end, I return the count.\n\n```\nfrom collections import defaultdict\n\nclass Solution(object):\n    def numMatchingSubseq(self, S, words):\n        """\n        :type S: str\n        :type words: List[str]\n        :rtype: int\n        """\n        word_dict = defaultdict(list)\n        count = 0\n        \n        for word in words:\n            word_dict[word[0]].append(word)            \n        \n        for char in S:\n            words_expecting_char = word_dict[char]\n            word_dict[char] = []\n            for word in words_expecting_char:\n                if len(word) == 1:\n                    # Finished subsequence! \n                    count += 1\n                else:\n                    word_dict[word[1]].append(word[1:])\n        \n        return count\n```
[]