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 and s 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) {}
  1. take a variable count and initially assign them 0. then return count
  2. now taking a for loop for brute forcing word is subsequence or not