- Published on
792 Number of matching subsequences
Problem
Given string s
and an array of words
, find the number of words[i]
that is a subsequences of s
.
Note:- 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.
Example
Input: s = "abcde", words = ["a", "bb", "acd", "ace"]
Output: 3
There are three words in words
array that are a subsequence of s
: "a", "acd", "ace".
Note:
- All words in
words
ands
will only consist of lowercase letters. - The length of
s
will be in the range of[1, 5000]
. - The length of
words
will be in the range of[1, 5000]
. - The length of
words[i]
will be in the range of[1, 50]
.
Solution
We have to check every element from the words
array with our given string s
. if any element of the array is a subsequence of s
then we will count it. so i am going to implement a brute force solution. for example, i am going to check "acd" is subsequence of "abcde" or not?
Note: I'll use Javascript to clarify, but the code will be made available in all languages
This is the boilerplate available on leetcode for JavaScript
/**
* @param {string} s
* @param {string[]} words
* @return {number}
*/
var numMatchingSubseq = function (s, words) {}
- take a variable
count
and initially assign them0
. then returncount
- now taking a for loop for brute forcing word is subsequence or not