Leetcode 792. Number of Matching Subsequences

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 three words in words that are a subsequence of S: "a", "acd", "ace".

Note:

• All words in words and S will only consists of lowercase letters.
• The length of S will be in the range of [1, 50000].
• The length of words will be in the range of [1, 5000].
• The length of words[i] will be in the range of [1, 50]

Brute Force Solution:

The most straight forward solution would be for each word in the words[], check with S and see if it's the subsequence of S. 

Code (Java):

class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int ans = 0;
        
        for (String word : words) {
            if (isSubsequence(S, word)) {
                ans++;
            }
        }
        
        return ans;
    }
    
    private boolean isSubsequence(String s, String w) {
        int sIndex = 0;
        int wIndex = 0;
        
        while (wIndex < w.length() && sIndex < s.length()) {
            if (s.charAt(sIndex) == w.charAt(wIndex)) {
                sIndex++;
                wIndex++;
            }
            else {
                sIndex++;
            }
        }
        
        return wIndex == w.length();
    }
}

Analysis:
The time complexity is O(S *(M + N)))
If we just compare two strings, the solution above is the best solution since we need to compare each character in the strings anyway. 

For this problem, however, since the length of the words is very big, it would be better if we can memorize something we did in the past.

A better solution (DP):