31 Sequence Pattern Matching

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false

------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:

PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.

[amitkumarsingh]

I don't know why I fully watched this videos, I already think the approach within a minute, this is just because you broo.. Thanks soo much, from the bottom of my heart <3

[mayurbhor]

Just a linear traversal in enough I guess to solve it. Maintain two pointers at each string, move one if you find the character in another. Not worth DP, but always good to know multiple ways of solving !

[sanketoreken]

2 pointer approach:

if we want to match string s with string t:

int pntr = 0;
for (int i=0; i<t.length(); i++) {
if (t[i] == s[pntr]) {
pntr++;
}
}

return pntr==s.length() ? true: false;

[trendingindia]

This guy will be remembered as a guy who made DP interesting and easy

[anant]

30 of 50 (60%) done! Others have mentioned a 2 ptr approach, but this LCS approach is also a diff way of thinking.

[shivanisheth]

after learning from ur videos i am now getting approaches within few minutes thank you for teaching dp in such great manner.

[priyakoshta]

You have built the concepts really nicely man. After following your all previous dp videos now I dont even wait for you to explain the solution, I just read the question take a pause and write the solution myself. But I still watch your video till the end so as to support you :)

[sanyamsinghal]

for this question, we can take two pointer i and j, i for larger string and j for smaller string
run a loop for bigger string:
if ith char of bigger == jth char of smaller THEN j++
now check if j==size then it is present




This can be done in O(N+M) time complexity instead O(N*M) by LCS

[jagrit]

Just by understanding the problem statement, LCS approach came to my mind. All thanks to your previous videos.

[SurajKumar-bwoi]

Leetcode (EASY):

LCS -> O(N*M)
2 Pointers -> O(N+M)

[mnsayeed]

Wildcard pattern matching is a more suitable candidate for DP than this one, since this can easily by solved using 2 pointer approach.

[aakashyadav]

Salute to people who cracked placements before feb 6, 2020 !

[rasenshuriken]

on leetcode this problem is called "is Subsequence"

[shrimadmishra]

I did not watch the full video because I was able to think of the logic and it is because of your sir. Thanks for this wonderful playlist.

[kohinoorkhan]

I have solved lot of DP question. because of you only bro ..thanks a lot for superb

[girishkulkarni]

I love your videos bro I wish we were taught algorithms in a similar way!!. I shared your videos with many friends they all call you GOD. Please try to make videos on other topics also thank you for this.

[prashant.s.]

30 out of 50 done, will finish in 2 days.this is literally better than web series

[vidhijain]

big thanks to make are life easy and developing our capacity to relate questions and think answers or solutions in a minute.

[hellosagar]

wow I'm also able to think about the approach before watching the video Thanks Aditya Sir

[arifwaqas]

I think this can be done n O(n) complexity using a stack,
reverse the given string and push it into the stack,
Loop through the second string and keep popping if same elements are found.
In the end, if (my_stack.empty()) return true; else return false.

Pls correct me if I am wrong but this would also give O(N)