Given string
S and a dictionary of words words, find the number of words[i] that is a subsequence of S.Example : Input: S = "abcde" words = ["a", "bb", "acd", "ace"] Output: 3 Explanation: There are 3 words in words that are a subsequence of S: "a", "acd", "ace".
Brute force Solution1
A brute force way to solve this problem is checking subsequence of S for each word. An outer loop is used to iterate all words. An inner loop is used to test if this word is a subsequence of S. If so, increase count by one.
Another brute force way is using an outer loop to iterate each character of S, and using an inner loop to iterate all words. If the first character of
words[i] equals to this character, remove it. Finally, count how many words are empty.For both methods, time complexity will be
O(words.size()) * O(S.size()).Improvement
When there is a one-to-many relation counting, one useful strategy will be using iteration of that 'one' as outer loop. And try to minimize the inner loop to iterate 'many'.
Thus we can improve second brute force by trying to reduce inner loop cost. If we can have a method to free us from iterating all words in each inner loop but only iterating those need to be trimmed, time cost can be reduced greatly to