LeetCode 792: Number of Matching Subsequences Solution

Master LeetCode problem 792 (Number of Matching Subsequences), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

792. Number of Matching Subsequences

Medium

Array Hash Table String Binary Search Dynamic Programming Trie Sorting

Problem Explanation

Explanation

To solve this problem, we can iterate over each word in the array and check if it is a subsequence of the given string s. We can do this by maintaining pointers for each word and the string s. We iterate over each character in the string and for each character in the word, we move the pointer in the word only if we find a match in the string.

Initialize a counter to keep track of the number of words that are subsequences of s.
For each word in the array:
- Initialize pointers wordPtr and sPtr to 0.
- Iterate over each character in the string s:
  - If the current character in s matches the character at wordPtr in the current word:
    - Increment wordPtr.
  - If wordPtr reaches the end of the word, increment the counter and break out of the loop.

At the end, return the counter which represents the number of words that are subsequences of s.

Time Complexity

The time complexity of this approach is O(n * m) where n is the length of the given string s and m is the average length of words in the array.

Space Complexity

The space complexity is O(1) as we are using only a constant amount of extra space.

Solution Code

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int count = 0;
        for (String word : words) {
            int wordPtr = 0, sPtr = 0;
            while (sPtr < s.length() && wordPtr < word.length()) {
                if (s.charAt(sPtr) == word.charAt(wordPtr)) {
                    wordPtr++;
                }
                sPtr++;
            }
            if (wordPtr == word.length()) {
                count++;
            }
        }
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 792 (Number of Matching Subsequences)?

This page provides optimized solutions for LeetCode problem 792 (Number of Matching Subsequences) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 792 (Number of Matching Subsequences)?

The time complexity for LeetCode 792 (Number of Matching Subsequences) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 792 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 792 in Java, C++, or Python.

Back to LeetCode Solutions