31 Sequence Pattern Matching

[@amitkumarsingh5414]

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

[@TheAdityaVerma]

Thanks brother, Do share to make this channel grow ! thought the credit is only yours ! You have a sharp mind !!

[@neghatnazir1668]

if lcs(a,b)==min(a.length(),b.length()); return true; else return false;

[@chaitanyakumar9229]

same bro, its cuz he taught before videos well

[@mrmagician5609]

same

[@navitabatra3019]

@@neghatnazir1668 , if we had to find a in b and a length is greater than b then also return false , there may be a chance you getting b substring in a.

[@trendingindia972]

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

[@mayurbhor2231]

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 !

[@iitibhupendrasingh6887]

yes true ``` class Solution { public: bool isSubsequence(string s, string t) { int n=s.length(); int m=t.length(); int i=n-1;int j=m-1; while(i>=0 and j>=0){ if(s[i]==t[j]){ i--;j--; }else{ j--; } } if(i==-1){ return true; } return false; } };```

[@sayakdas6726]

True

[@sayakdas6726]

bool solveRecursive(string &S,string &L,int n,int m){ if(n > m) return false; if(n==0) return true; if(S[n-1] == L[m-1]) return solveRecursive(S,L,n-1,m-1); else return solveRecursive(S,L,n,m-1); } bool isSubsequence(string s, string t) { return solveRecursive(s,t,s.length(),t.length()); }

[@jatinbhatoya8420]

boolean isSubSequence(String s1, String s2){ int i=0,j=0; while(i

[@killeraloo3247]

bool isSubSequence(string A, string B) { int j=0; for(int i=0;i

[@sanketoreken2980]

2 pointer approach: if we want to match string s with string t: int pntr = 0; for (int i=0; i

[@AliShair-f7q]

its helpful

[@S4hil_Yadav]

nice but the ternary operator is not needed

[@0anant0]

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

[@aadityasharma6855]

1d dp cover nhi h isme

[@akshaibaruah1720]

stop bro please don't spoil comment section

[@shivanisheth186]

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

[@priyakoshta7129]

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 :)

[@sanyamsinghal7992]

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

[@TheAdityaVerma]

Yeah but thats not intuitive brother, I can give you one more optimized solution but that would be just you mugging it up, try to come up with the solutions !!

[@sanyamsinghal7992]

@@TheAdityaVerma you are right that may not be intitutive, I was just doing a question where time constraints were O(N) that's when I came up with this. Btw if there is another more optimized approach then please share

[@najimali32]

@@TheAdityaVerma How can that's not the intuitive first thing that came in my mind is two pointers approached. Your method is good but you can also share another method that is more optimized.

[@paraslaul3307]

please share code

[@hackingguy]

@@TheAdityaVerma Two Pointer Approach Came By Intution, Never Mugged Up!

[@jagrit07]

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

[@TheAdityaVerma]

Glad to hear that, please subscribe and share to help this channel grow !!

[@SurajKumar-bw9oi]

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

[@dhruvsharma7964]

please share question link

[@kohinoorkhan8529]

ya we can do same question with one for loop.(THINK LITTLE BIT !).

[@praveengautam9851]

@@kohinoorkhan8529 yup...just traverse the bigger string and check for smaller string ...

[@sayantaniguha8519]

bool isSubSequence(string A, string B) { int j = 0, i = 0; while ( i < B.size() && j < A.size() ) { if (A[j] == B[i]) j++; i++; } return ( j == A.size() ); } Iye hi hai 2-pointers wala solution?

[@dhruvsharma7964]

@@apoorvkrishan1447 Thank you.

[@rasenshuriken6333]

on leetcode this problem is called "is Subsequence"

[@aakashyadav6228]

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

[@mnsayeed999]

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

[@abhinavtyagi1804]

with two pointers this will be O(n) optimized, not worth LCS approach

[@abhineetsarkar3456]

Before watching this playlist, I used to skip the DP problems. Thanks to @Aditya Verma, seeing this problem I give it a try and boom, solved in just 2 attempts. Thank You @Aditya Verma from the bottom to my heart. 😊❤

[@sayanghosh2883]

even two pointer is not required just a linear scan is enough

[@vikranttandon6253]

Exactly! A linear scan would do it 🧐

[@cherupawan3777]

@@sayanghosh2883 how can u elaborate

[@ngtv5608]

Need a playlist on GRAPH !!

[@shrimadmishra3615]

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.

[@prashant.s.397]

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

[@kohinoorkhan8529]

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

[@abhishekbabbar9234]

Bro, can u tell us more questions on sequence pattern matching?

[@vinaybansal2430]

Find number of times a string occurs as a subsequence in given string

[@VishalKumar-xr4nm]

DP is good to understand concept of subsequence. Following is optimal way to do the same Time complexity: O( min(s.length() ,t.length() ) ) Space complexity: O( 1 ) class Solution { public boolean isSubsequence(String s, String t) { int m = s.length(), n = t.length(); if(m>n) return false; int j = 0; for(int i=0; j

[@psibarpsi]

Time complexity will be O (max (|a|, |b|)).

[@arifwaqas698]

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)

[@codekro6060]

U r right

[@kxnyshk]

@@codekro6060 how will you push the string into the stack, index by index? Just by traversing it or is there a better way in JAVA or C++ to do it?

[@codekro6060]

@@kxnyshk u can create a stack of type string

[@ritikshrivastava9442]

no need of using extra memory we can do it in O(1) extra space bool isSubSequence(string A, string B) { int j=0; for(int i=0; i

[@shubhamsharma-ec3re]

One more way for this : a=input() b=input() f=0 for i in a: if i in b: ind=b.index(i) b=b[ind:] f+=1 print(f==len(a))

[@RohitBindalMusic]

Thanks for amazing explanation. Also it can be done in O(N) time and O(1) space: bool isSubSequence(string A, string B) { // code here int n = A.length(); int m = B.length(); int i=0,j=0; while(i

[@SKEager02]

👍

[@girishkulkarni1702]

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.

[@TheAdityaVerma]

Thanks for sharing!! Sure, will be uploading more videos soon, kinda stuck now due to lockdown as everybody else. 😕

[@hellosagar]

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

[@shivammishra-sj8jo]

Bro your teaching methodology is awesome and very useful to correlate with other subproblems

[@vidhijain4554]

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

[@umber3117]

Excellent videos.Thanks for sharing!!! Really excited to see your subscribers are growing.

[@beingnitian2745]

bool isSubsequence(string s, string t) { int k=0;int j=0; for(int i=0; i

[@harpic949]

Try leetcode 10 and 44 . Must try dp questions on pattern matching.

[@no_mercy7366]

we can solve it directly also by dp,we will check two conditions if a[i-1]==b[j-1] then return true&&dp[i-1][j-1] otherwise return false||dp[i][j-1] like this we can simply return dp[a.size()][b.size()] at the end

[@niladribiswas1211]

I have done this by your previous video LRS. First combine 2 string then find longest repeating sequence if it matches with original then true

[@jnukrish]

Your video is really very nice. Just a suggestion! It would be better,if you can also explain the time complexity of your solutions.

[@deepak-ly3ob]

Wonderful lectures.

[@kritartha007]

The question can be solved with the help of queue. Put String 'a' in Queue, q1; String 'b' in Queue, q2. Now, traverse q1 and q2 from starting and check for the front element of q1 in q2. If it matches, then pop the front element of q1 and q2. If it doesn't , then pop the first element of q2 and carry on. After traversing the loop completely, if q1 is still not empty then a is not a subsequence of b.

[@kritartha007]

So, by now we got three approach for the problem: Queues, two pointers, dp.

[@charan775]

bro where are questions on LIS & DP on grid?

[@sumantopal558]

isko LIS nahi aata.

[@nikhilraj5115]

@@sumantopal558 isko jitna aata hai, utna toh seekh le

[@sumantopal558]

@@nikhilraj5115 hum toh college dropout hai... Dukaan pe baithke agle 80 saal nikalne waale hai

[@usurper1091]

@@sumantopal558 ungratefulness ki bhi seema hoti hai

[@VishalSharma-hq5ti]

@@sumantopal558 toh dukaan par baith na chupchap!

[@DamnConfusion]

Why not using two pointers one on string a another on string b. In that case, time complexity: O(m+n) space complexity: O(1)

[@chiragkhemani1615]

we can here just use stack to store string a and iterate from backwards of string b and then check

[@akashkumarsingh5355]

@aditya_verma plzz..upload wildcard matching problem

[@jayantgangwani7336]

Agar ye poocha ho ki count the no. Of subsequences of one string s that equals another string t ,then what to do

[@sakshisinha8164]

This question is not wildcard pattern matching, right?

[@zeta_meow_meow]

that length sirf kaam kar jaega concept was great....i was using printLCS .... nice concept of LCS Range E {0 , min(a,b)} 🥰🫶🥰

[@syedhabeebuddin101]

I think we can use Two pointer approach, It would be better.

[@pratikkumar6148]

Can this code be further optimized for some kind of inputs ? for e.g. *S1.length > S2.length* then surely *S1* can't be LCS of *S2* if ( S1.length > S2.length ) return false if( S1.length==LCS(S1,S2) ) return true return false

[@adityajain4125]

Sir, can't we check character by character and move in "a" only when matched else move in "b" and if matched then move in both? until one ends

[@panavkumar9009]

Yes we can do that but that is the naive approach and most probably using that would give you a time limit error(TLE).

[@thinkingmad1685]

@@panavkumar9009 lol how come it will be efficient just a single while loop is needed

[@vishnuagrawal5730]

plz also share pratice questions on relevant topic.

[@shubhampandey7177]

2 pointer approach simple and easy to use bool isSubsequence(string s, string t) { if (s.size() > t.size()) return false; int ptr = 0; for(int i =0;i

[@PrabhunathYadav]

I have solved it using 2 approaches: package sample.dp.problems.lcs; public class SequencePatternMatching { public static void main(String[] args) { String a="AXY"; String b="ADXCPY"; logicalApproch(a, b); int lcsLen= lcs(a, b, a.length()-1, b.length()-1); System.out.println(lcsLen==a.length()); } public static int lcs(String s1, String s2, int i, int j){ if(i b.length()){ System.out.println(false); }else{ int i=0; int j=0; while(i< a.length() && j< b.length()){ if(a.charAt(i)== b.charAt(j)){ i++; j++; }else{ j++; } } if(i== a.length()){ System.out.println(true); }else{ System.out.println(false); } } } }

[@MASTER0123TBG]

please cover LIS also

[@vakhariyajay315]

Thank you very much. You are a genius.

[@rohit_ae]

*Without using DP* bool is_sub_sequence(string &s1, string &s2, int m, int n) { int i = m-1; int j = n-1; while(j >= 0) { if(s1[i] == s2[j]) i--; j--; } return i == -1 ? 1 : 0; } TC: O(N) SC: O(1) *Using DP* : int isSequence(string &s1, string &s2, int m, int n) { vector< vector > dp(m + 1, vector(n+1, 0)); for (int i = 1; i < m+1; i++) { for (int j = 1; j < n+1; j++) { if(s1[i-1] == s2[j-1]) dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = max( dp[i-1][j], dp[i][j-1] ); } } return dp[m][n]; } string s1 = "AXY"; string s2 = "YADXCPY"; cout

[@masiamahmed]

why use O(n*m) time complexity where we can solve it in O(n+m) time complexity .

[@gagneetsinghbadgaal1026]

well you can also solve this using 2 pointer approach with o(n) tc

[@shubhamshrivastava8649]

I have one approach , we can have length of string a in i and length of string b in j. We run a loop till any one of i and j gets 0. now we will check what is 0 now, if i is 0, we return YES else we return NO i will become 0 only when string b has every character of string a (sequentially), otherwise j will become 0 first. see below : while(i && j) { if(a[i-1] == b[j-1]) { i--; j--;} else { j--;} } if(i==0) return "YES"; else return "NO";

[@MALIWAL1000]

*# Recursive Approach* The idea is simple, we traverse both strings from one side to other side (say from rightmost character to leftmost). If we find a matching character, we move ahead in both strings. Otherwise we move ahead only in str2. Code: class Solution { public: bool isSubSeq(string str1, string str2, int m, int n) { // Base Cases if (m == 0) return true; if (n == 0) return false; // If last characters of two strings are matching if (str1[m-1] == str2[n-1]) return isSubSeq(str1, str2, m-1, n-1); // If last characters are not matching return isSubSeq(str1, str2, m, n-1); } bool isSubsequence(string s, string t) { int m = s.size(); int n = t.size(); return isSubSeq(s,t,m,n); } }; // Approach Using TWO POINTER class Solution { public: bool isSubsequence(string s, string t) { int m = s.size(); int n = t.size(); int i = 0, j = 0; while(i < m && j < n) { if(s[i] == t[j]) { i++; } j++; } return i == m ? 1 : 0; } }; // USING DYNAMIC PROGRAMMING // if LCS of string A nd B is equal to Size of String A then its True else false; class Solution { public: int helper(string x, string y) { int m = x.size(); int n = y.size(); int dp[m+1][n+1]; for(int i = 0; i

[@killeraloo3247]

c++ easy solution below-- int i=0; for(int j=0;j

[@gokusaiyan1128]

can't we do it with two pointer approach too ?

[@codeguru9543]

Thanks for this tutorial

[@hridayjyotiborkakati3449]

bool isSubsequence(string s, string t) { int i=0; for(int j=0;j

[@code7434]

Bhai wildcard pattern matching daal do

[@shubhamprashar7676]

😅 😅 Is this wrong? def check(str1,str2): curr = 0 for i in range(len(str1)): if str1[i] == str2[curr]: curr +=1 return curr >= len(str2) str1 = "ADXCPY" str2 = "AXY" print(check(str1,str2))

[@aizazahammad2593]

Does anyone know how to solve count palindromic subsequences?

[@RishuKumar-mn2jo]

Bro can u please upload the recursive video approach? I am not able to form the choice diagram.

[@YashSharma-dz7uu]

#include #include using namespace std; bool ans(string s1, string s2, int n, int m) { if (n == 0) { return true; } if (m == 0) { return false; } if (s1[n - 1] == s2[m - 1]) { return true && ans(s1, s2, n - 1, m - 1); } return ans(s1, s2, n, m - 1); } int main() { string s1, s2; cin >> s1; cin >> s2; int l1 = s1.size(); int l2 = s2.size(); if (ans(s1, s2, l1, l2)) { cout

[@raj-nq8ke]

LEETCODE Question Name : Is Susequence (EASY)

[@ritikagupta8847]

@Aditya we will return true even if len(LCS) > len(str1)?? or only if they are equal. I am a little confused with question

[@gurnoorsingh2954]

LCS str1 se badha nhi ho sakta Maximum voh equal ho sakta

[@tekbssync5727]

​@@gurnoorsingh2954 LCS wala code send kardo bhai , mera segmentation fault dikha rha

[@_Mindfield]

First of all thank you for putting your efforts in creating content 🙂 Why can't we do it like this in O(n) time? boolean isSubsequence(String src, String s) { int j=0; for(int i=0;i

[@abhimanyujena191]

We can solve it using stacks with O(n) time

[@deepugupta8440]

This type of same question is asked in Google Kickstart round a 2022 ...😁

[@Education_2753]

Sir ,you doing great work sir thanks from the core of my heart ❤️❣️ sir And plz upload the complete playlist of dp sir 🙏🙏

[@sumanhowlader3657]

can anyone paste the link where i can get this practice problem of Sequence Pattern Matching?

[@shwetanknaveen]

Someone please give the link of the question here

[@surajpawar1812]

#include using namespace std; int main() { string a="axyy"; string b="adxcpy"; int n=a.size(); int m=b.size(); int j=0; for(int i=0;i

[@PiyushCodes-ph3hl]

Bhaiya please DP series complete kardo

[@krishnendughosh2368]

return lcs==a.length || lcs==b.length is giving me TLE in GFG only 232 tests are passing.

[@priyankasetiya1358]

class Solution { private int lcs(String s,String t){ int m=s.length(); int n=t.length(); int[][] dp=new int[m+1][n+1]; for(int i=1;i

[@adarshsasidharan254]

more optimised is a two pointer solution O(N)

[@khemendrabhardwaj2552]

Can't we dont it using 2 pointer technique

[@nikunjgupta2878]

Sir please upload question related to sequence pattern maching.....

[@TheAdityaVerma]

Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️

[@tekbssync5727]

@@TheAdityaVerma these two lines are copy pasted. i have seen this in 15-16 comments😂 *Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️*

[@abhilasharaj7991]

Plz make video on greedy algo also

[@Journeywithasmile]

how to find time complexity of these algorithm someone plz help

[@YashSharma-dz7uu]

Recursive Approach : #include #include using namespace std; bool ans(string s1, string s2, int n, int m) { if (n == 0) { return true; } if (m == 0) { return false; } if (s1[n - 1] == s2[m - 1]) { return true && ans(s1, s2, n - 1, m - 1); } return ans(s1, s2, n, m - 1); } int main() { string s1, s2; cin >> s1; cin >> s2; int l1 = s1.size(); int l2 = s2.size(); if (ans(s1, s2, l1, l2)) { cout

[@vivekmishra641]

Could have been solved with two pointer approach too.

[@ayushbisht2689]

Result = t[n][m] If(result== min(n,m){ Return true; } Else{ Return false; }

[@sainirj20]

public boolean isSubsequence(String s, String t) { if(s.length()==0) return true; int i=0; int j=0; while(i

[@vidyabhushan7655]

#Looping through string int i=s.length()-1, j=t.length()-1; while(i>=0 && j>=0){ if(s[i]==t[j]) {i--; j--;} else j--; } return i

[@divyam-hx3ie]

// Sequence Pattern Matching #include using namespace std; int LCS(string a , string b , int n , int m){ if(n==0 || m==0) return 0; vector dp(n+1,vector(m+1)); dp[n][m]= 0; for(int i=n-1;i>=0;--i){ for(int j=m-1;j>=0;j--){ if(a[i+1]==b[j+1]){ dp[i][j] = 1 + dp[i+1][j+1]; } else{ dp[i][j] = max(dp[i+1][j] , dp[i][j+1]); } } } return dp[0][0]; } int main(){ string a,b; cin>>a>>b; int n = a.length(); int m = b.length(); int lcs = LCS(a,b,n,m); if(lcs >= n) cout

[@nikitajaiswal9112]

class Solution: def isSubsequence(self, s: str, t: str) -> bool: lcs=self.longestCommonSubsequence(s,t) if len(s)==lcs: return True return False def longestCommonSubsequence(self, text1, text2): m = len(text1) n = len(text2) t = [[0]*(n+1) for i in range(m+1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i-1] == text2[j-1]: t[i][j] = t[i-1][j-1] + 1 else: t[i][j] = max(t[i][j - 1], t[i - 1][j]) return t[m][n]

[@nidhishsinghal5167]

Bro need series on recursion and backtracking

[@funenjoynilaypatel4553]

17 SEP 2022

[@yash_renaissance_athlete]

Love your videos bro. Lovely explanations. But I got another idea. This can be done through using stack or queue in O(N) time and O(M) space. This is how I did it with stack def seq_pat_match(a, b): stack_a = [] ## populating the stack the stack in such a way that the first character of a is on top reversed_a = a[::-1] for char in reversed_a: stack_a.append(char) ##### stack_a would look like this for a="axy" # a

[@mental-block]

As other's suggested this is DP series. But yeah If you want to use other method then I don't think you don't even need any auxiliary space. See this solution - public boolean isSubsequence(String s, String t) { if(s == null || t == null || s.length() > t.length() ) return false; if(s.length() == 0 && t.length() == 0) return true; int i =0; for(int j=0; i

[@NotOmnipotent69]

we can solve this with 2 pointer approach

[@shankysays]

Lcs is overkill for this. Just do linear search or use hashmap and solve in o(n).

[@Shoeb647]

This particular problem can be solved without dp :

[@ritiksahu5310]

one approach can be if(i==0&& j==0)return true; else if(i==0 ||j==0) return false; if(s.charAt(i-1)==s.charAt(j-1))return fn(i-1,j-1); else return fn(i,j-1); time O(N) space O(N) (recursion stack

[@vipulgupta3915]

Hi Aditya, This question can be solved as : boolean isSubSequence(String A, String B) { { int i = 0, j = 0; while (i < A.length() && j < B.length()) { if (A.charAt(i) == B.charAt(j)) { i++; j++; } else j++; } if (i == A.length()) return true; return false; } }

[@prabhatmishra5667]

bool isSubsequence(string s, string t) { int m = s.length(); int n = t.length(); if(m==0) return true; bool flag = false; int i=0; int j=0; while(i

[@shubhambodake7778]

Leetcode Problem : leetcode.com/problems/is-subsequence/

[@cricsinghvlogz]

please make a playlist on backtracking and recursion

[@dilipsuthar4206]

Ye question kaha par hai

[@LightYagami-ib6fb]

leetcode.com/problems/is-subsequence/

[@niru1931]

nice

[@ankitraj4179]

Simple as fuck. @adityaverma Bhaiya time complexity jyada aa rhi thi dp ke approach se boolean isSubSequence(String A, String B){ int n = A.length() , m = B.length() ; int i = 0 , j = 0 ; while(i < n && j < m){ if(A.charAt(i) == B.charAt(j)){ i++ ; j++ ; }else{ j++ ; } } if( i == n){ return true ; } return false ; } }