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 call insert for each word and finally dfs 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