792. Number of Matching Subsequences LeetCode Solution
In this guide, you will get 792. Number of Matching Subsequences LeetCode Solution with the best time and space complexity. The solution to Number of Matching Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Matching Subsequences
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.
For example, “ace” is a subsequence of “abcde”.
Example 1:
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”.
Example 2:
Input: s = “dsahjpjauf”, words = [“ahjpjau”,”ja”,”ahbwzgqnuk”,”tnmlanowax”]
Output: 2
Constraints:
1 <= s.length <= 5 * 104
1 <= words.length <= 5000
1 <= words[i].length <= 50
s and words[i] consist of only lowercase English letters.
Complexity Analysis
Time Complexity: O(|\texttt{s}| + \Sigma |\texttt{words[i]}|)
Space Complexity: O(\Sigma |\texttt{words[i]}|)
792. Number of Matching Subsequences LeetCode Solution in C++
struct TrieNode {
vector<shared_ptr<TrieNode>> children;
int count = 0;
TrieNode() : children(26) {}
};
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
for (const string& word : words)
insert(word);
return dfs(s, 0, root);
}
private:
shared_ptr<TrieNode> root = make_shared<TrieNode>();
void insert(const string& word) {
shared_ptr<TrieNode> node = root;
for (const char c : word) {
const int i = c - 'a';
if (node->children[i] == nullptr)
node->children[i] = make_shared<TrieNode>();
node = node->children[i];
}
++node->count;
}
int dfs(const string& s, int i, shared_ptr<TrieNode> node) {
int ans = node->count;
if (i >= s.length())
return ans;
for (int j = 0; j < 26; ++j)
if (node->children[j]) {
const int index = s.find('a' + j, i);
if (index != -1)
ans += dfs(s, index + 1, node->children[j]);
}
return ans;
}
}; /* code provided by PROGIEZ */
792. Number of Matching Subsequences LeetCode Solution in Java
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public int count = 0;
}
class Solution {
public int numMatchingSubseq(String s, String[] words) {
for (final String word : words)
insert(word);
return dfs(s, 0, root);
}
private TrieNode root = new TrieNode();
private void insert(final String word) {
TrieNode node = root;
for (final char c : word.toCharArray()) {
final int i = c - 'a';
if (node.children[i] == null)
node.children[i] = new TrieNode();
node = node.children[i];
}
++node.count;
}
private int dfs(final String s, int i, TrieNode node) {
int ans = node.count;
if (i >= s.length())
return ans;
for (int j = 0; j < 26; ++j)
if (node.children[j] != null) {
final int index = s.indexOf('a' + j, i);
if (index != -1)
ans += dfs(s, index + 1, node.children[j]);
}
return ans;
}
} // code provided by PROGIEZ
792. Number of Matching Subsequences LeetCode Solution in Python
class Solution:
def numMatchingSubseq(self, s: str, words: list[str]) -> int:
root = {}
def insert(word: str) -> None:
node = root
for c in word:
if c not in node:
node[c] = {'count': 0}
node = node[c]
node['count'] += 1
for word in words:
insert(word)
def dfs(s: str, i: int, node: dict) -> int:
ans = node['count'] if 'count' in node else 0
if i >= len(s):
return ans
for c in string.ascii_lowercase:
if c in node:
try:
index = s.index(c, i)
ans += dfs(s, index + 1, node[c])
except ValueError:
continue
return ans
return dfs(s, 0, root) # code by PROGIEZ
