Leetcode 792. Number of Matching Subsequences

Accepted Code

Problem Statement

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of 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.

  • For example, "ace" is a subsequence of "abcde".

Test Cases

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

Constraints

  • 1 <= s.length <= 5 * 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 50
  • s and words[i] consist of only lowercase English letters.

Approach

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.

Algorithm

  1. Traverse through the word array.
  2. Check whether this word is a subsequence of string s.
  3. For that traverse through each and every character of the word and just make use of indexOf() method.
  4. 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
  5. 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).

Code

Java Code

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Rohith Vazhathody

Rohith Vazhathody

Software Engineer | Weekly articles | Interested in DSA, design | Writes about problem solving, algorithm explanation of my understanding and Java Codes.