792. Number of Matching Subsequences

Problem Description

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Examples:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

Constraints:

• 1 ≤ s.length ≤ 5 * 10^4
• 1 ≤ words.length ≤ 5000
• 1 ≤ words[i].length ≤ 50
• s and words[i] consist of only lowercase English letters

Python Solution

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        def is_subsequence(word: str) -> bool:
            it = iter(s)
            return all(c in it for c in word)
            
        count = 0
        for word in words:
            if is_subsequence(word):
                count += 1
        return count

Implementation Notes:

• Uses iterator to check subsequence efficiently
• For each word, checks if it's a subsequence of s
• Time complexity: O(n * m) where n is length of s and m is total length of words
• Space complexity: O(1)

Java Solution

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int count = 0;
        for (String word : words) {
            if (isSubsequence(s, word)) {
                count++;
            }
        }
        return count;
    }
    
    private boolean isSubsequence(String s, String word) {
        int j = 0;
        for (int i = 0; i < s.length() && j < word.length(); i++) {
            if (s.charAt(i) == word.charAt(j)) {
                j++;
            }
        }
        return j == word.length();
    }
}

C++ Solution

class Solution {
private:
    bool isSubsequence(const string& s, const string& word) {
        int j = 0;
        for (int i = 0; i < s.length() && j < word.length(); i++) {
            if (s[i] == word[j]) {
                j++;
            }
        }
        return j == word.length();
    }
    
public:
    int numMatchingSubseq(string s, vector& words) {
        int count = 0;
        for (const string& word : words) {
            if (isSubsequence(s, word)) {
                count++;
            }
        }
        return count;
    }
};

JavaScript Solution

function numMatchingSubseq(s, words) {
    function isSubsequence(word) {
        let j = 0;
        for (let i = 0; i < s.length && j < word.length; i++) {
            if (s[i] === word[j]) {
                j++;
            }
        }
        return j === word.length;
    }
    
    let count = 0;
    for (const word of words) {
        if (isSubsequence(word)) {
            count++;
        }
    }
    return count;
}

C# Solution

public class Solution {
    public int NumMatchingSubseq(string s, string[] words) {
        int count = 0;
        foreach (string word in words) {
            if (IsSubsequence(s, word)) {
                count++;
            }
        }
        return count;
    }
    
    private bool IsSubsequence(string s, string word) {
        int j = 0;
        for (int i = 0; i < s.Length && j < word.Length; i++) {
            if (s[i] == word[j]) {
                j++;
            }
        }
        return j == word.Length;
    }
}

Implementation Notes:

• Uses two pointers to check subsequence efficiently
• For each word, checks if it's a subsequence of s
• Time complexity: O(n * m) where n is length of s and m is total length of words
• Space complexity: O(1)