Leetcode 792. Number of Matching Subsequences
Problem Explanation
In this problem, we have a string S
and a list of words words
. The task is to find the number of words in words
that are subsequences of the string 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.
Walk through Example
For instance consider an example:
1Input: 2S = "abcde" 3words = ["a", "bb", "acd", "ace"] 4Output: 3
Here you can see that, "a", "acd" and "ace" are subsequences of "abcde", but "bb" is not.
To solve this problem, we can use Trie data structure. First, we initialize an empty root node of a Trie. Then we iterate through the list of words. For each word, we insert it into the Trie.
After constructing the Trie, we perform a depth-first search on the string S. Starting from the root, we recursively check each character in the string S using the dfs
function. Whenever we find a match, we move forward in the Trie as well as in the string, and increment the answer by the count of current Trie node.
Python Solution
1 2python 3class TrieNode: 4 def __init__(self): 5 self.children = [None]*26 6 self.count = 0 7 8class Solution: 9 def numMatchingSubseq(self, S: str, words) -> int: 10 self.root = TrieNode() 11 for word in words: 12 self.insert(word) 13 14 return self.dfs(S, 0, self.root) 15 16 def insert(self, word): 17 node = self.root 18 for c in word: 19 i = ord(c) - ord('a') 20 if not node.children[i]: 21 node.children[i] = TrieNode() 22 node = node.children[i] 23 node.count += 1 24 25 def dfs(self, s, i, node): 26 ans = node.count 27 if i >= len(s): 28 return ans 29 for j in range(26): 30 if node.children[j]: 31 index = s.find(chr(j + ord('a')), i) 32 if index != -1: 33 ans += self.dfs(s, index + 1, node.children[j]) 34 return ans
Java Solution
1 2java 3class Solution { 4 private TrieNode root = new TrieNode(); 5 6 public int numMatchingSubseq(String S, String[] words) { 7 for(String word : words) 8 insert(word); 9 10 return dfs(S, 0, root); 11 } 12 13 class TrieNode { 14 TrieNode[] children = new TrieNode[26]; 15 int count = 0; 16 } 17 18 private void insert(String word) { 19 TrieNode node = root; 20 for(char c : word.toCharArray()) { 21 final int i = c - 'a'; 22 if(node.children[i] == null) 23 node.children[i] = new TrieNode(); 24 node = node.children[i]; 25 } 26 27 ++node.count; 28 } 29 30 private int dfs(String s, int i, TrieNode node) { 31 int ans = node.count; 32 if(i >= s.length()) 33 return ans; 34 35 for(int j = 0; j < 26; ++j) 36 if(node.children[j] != null) { 37 final int index = s.indexOf('a' + j, i); 38 if(index != -1) 39 ans += dfs(s, index + 1, node.children[j]); 40 } 41 return ans; 42 } 43}
Javascript Solution
1 2javascript 3 4class TrieNode { 5 constructor() { 6 this.children = new Array(26); 7 this.count = 0; 8 } 9} 10 11var numMatchingSubseq = function(S, words) { 12 let root = new TrieNode(); 13 14 words.forEach(word => { 15 insert(word, root); 16 }); 17 18 return dfs(S, 0, root); 19 20 function insert(word, root) { 21 let node = root; 22 for(let c of word) { 23 let i = c.charCodeAt(0) - 'a'.charCodeAt(0); 24 if(!node.children[i]) { 25 node.children[i] = new TrieNode(); 26 } 27 node = node.children[i]; 28 } 29 node.count += 1; 30 } 31 32 function dfs(s, i, node) { 33 let ans = node.count; 34 if(i >= s.length) { 35 return ans; 36 } 37 for(let j = 0; j < 26; ++j) { 38 if(node.children[j]) { 39 let index = s.indexOf(String.fromCharCode(j + 'a'.charCodeAt(0)), i); 40 if(index != -1) { 41 ans += dfs(s, index + 1, node.children[j]); 42 } 43 } 44 } 45 return ans; 46 } 47};
Explanation of significant steps
insert
: It is a helper function that generates a TrieNode for each character in the word and finally increments in the count of the final node of the word.dfs
: It is a recursive function which traverses the entire string S in depth-first order. It keeps track of the pointer in our Trie and return the count of the final TrieNode.- In the main function
numMatchingSubseq
, we simply callinsert
for each word and finallydfs
in string S, and return the result.In the above solutions, Trie data structure is used to solve the problem. Let's delve deeper into the working of significant steps:
1. Insertion in Trie:
We start by iterating through each word and calling the insert
function which is a helper function that does exactly what its name suggests, it inserts nodes corresponding to each character in Trie tree, starting from the root node. Moreover, for each word in the list, we increment a counter associated with each TrieNode.
1
2python
3def insert(self, word):
4 node = self.root
5 for c in word:
6 i = ord(c) - ord('a') # gets the index corresponding to the charachter
7 if not node.children[i]: # if child node does not exist, create one
8 node.children[i] = TrieNode()
9 node = node.children[i] # move to next node
10 node.count += 1 # increment count in the final node
2. Depth First Search in Trie:
Once we have created the Trie tree with all the words in our list of words, we call the dfs
(depth-first search) function which will traverse all characters in given string 'S' in depth first order.
For each character in the string, we traverse down the trie in depth manner (from left to right). This is achieved by using recursion (function calling itself). We keep comparing each character with the children nodes of Trie tree and move ahead in Trie tree when a match is found.
1
2python
3def dfs(self, s, i, node):
4 ans = node.count # Answer would at least be the count of nodes visited till this point
5 if i >= len(s): # if reached end of string, return answer
6 return ans
7 for j in range(26): # check for all possible characters
8 if node.children[j]: # if child node exists
9 index = s.find(chr(j + ord('a')), i) # try to find a match in string 's'
10 if index != -1: # if the character was found in 's'
11 ans += self.dfs(s, index + 1, node.children[j]) # move to next character in 's' and child node in trie
12 return ans
3. Main Function:
Lastly, the main function numMatchingSubseq
takes the string and list of words as arguments, initializes an instance of TrieNode as root, inserts each word in the list to Trie by calling insert
and ultimately return the answer by calling dfs
.
1
2python
3def numMatchingSubseq(self, S: str, words) -> int:
4 self.root = TrieNode() # Initialize root node
5 for word in words: # For each word in list
6 self.insert(word) # Insert word in Trie
7 return self.dfs(S, 0, self.root) # return the number of words which are subsequence of given string
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.