Leetcode 792. 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
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
Input: s = "abcde", words = ["a","bb","acd","ace"]
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".
Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
1 <= s.length <= 5 * 104
1 <= words.length <= 5000
1 <= words[i].length <= 50
words[i]consist of only lowercase English letters.
Let’s try to do what the problem asks us. Traverse through the words array and take out each and every word from that array. Now just check whether this word is a subsequence of the string s. Thats it. If it is present we increment the count and finally return that count.
- Traverse through the word array.
- Check whether this word is a subsequence of string s.
- For that traverse through each and every character of the word and just make use of indexOf() method.
- Track the previous index which is initially zero and update with previousindex = index + 1 if index is not -1.
Note : index = s.indexOf(ch, previousIndex)
index == -1, then return false, otherwise
previousindex = index + 1
- Finally return the counter which we are tracking whenever we see any subsequence.
Time and Space Complexity
Let’s say, size of the word array is length, size of the string is n and maximum size of the word inside the word array is p. Then the time complexity will be O(length² * n * p).
There are no extra space we are using, so space complexity will be O(1).