31 Sequence Pattern Matching
Вставка
- Опубліковано 5 жов 2024
- 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
Problem Link: leetcode.com/p...
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
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.
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
Thanks brother, Do share to make this channel grow ! thought the credit is only yours ! You have a sharp mind !!
if lcs(a,b)==min(a.length(),b.length());
return true;
else
return false;
same bro, its cuz he taught before videos well
same
@@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.
This guy will be remembered as a guy who made DP interesting and easy
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 !
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;
}
};```
True
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());
}
boolean isSubSequence(String s1, String s2){
int i=0,j=0;
while(i
bool isSubSequence(string A, string B)
{
int j=0;
for(int i=0;i
2 pointer approach:
if we want to match string s with string t:
int pntr = 0;
for (int i=0; i
its helpful
30 of 50 (60%) done! Others have mentioned a 2 ptr approach, but this LCS approach is also a diff way of thinking.
1d dp cover nhi h isme
stop bro please don't spoil comment section
after learning from ur videos i am now getting approaches within few minutes thank you for teaching dp in such great manner.
Just by understanding the problem statement, LCS approach came to my mind. All thanks to your previous videos.
Glad to hear that, please subscribe and share to help this channel grow !!
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 :)
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
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 !!
@@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
@@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.
please share code
@@TheAdityaVerma Two Pointer Approach Came By Intution, Never Mugged Up!
Leetcode (EASY):
LCS -> O(N*M)
2 Pointers -> O(N+M)
please share question link
ya we can do same question with one for loop.(THINK LITTLE BIT !).
@@kohinoorkhan8529 yup...just traverse the bigger string and check for smaller string ...
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?
@@apoorvkrishan1447 Thank you.
Salute to people who cracked placements before feb 6, 2020 !
on leetcode this problem is called "is Subsequence"
Wildcard pattern matching is a more suitable candidate for DP than this one, since this can easily by solved using 2 pointer approach.
with two pointers this will be O(n) optimized, not worth LCS approach
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. 😊❤
even two pointer is not required just a linear scan is enough
Exactly! A linear scan would do it 🧐
@@sayanghosh2883 how can u elaborate
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.
Need a playlist on GRAPH !!
I have solved lot of DP question. because of you only bro ..thanks a lot for superb videos.....
Bro, can u tell us more questions on sequence pattern matching?
Find number of times a string occurs as a subsequence in given string
big thanks to make are life easy and developing our capacity to relate questions and think answers or solutions in a minute.
30 out of 50 done ,will finish in 2 days.this is literally better than web series
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.
Thanks for sharing!! Sure, will be uploading more videos soon, kinda stuck now due to lockdown as everybody else. 😕
wow I'm also able to think about the approach before watching the video Thanks Aditya Sir
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
👍
Bro your teaching methodology is awesome and very useful to correlate with other subproblems
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
Time complexity will be O (max (|a|, |b|)).
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))
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)
U r right
@@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?
@@kxnyshk u can create a stack of type string
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
Your video is really very nice. Just a suggestion! It would be better,if you can also explain the time complexity of your solutions.
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
Try leetcode 10 and 44 . Must try dp questions on pattern matching.
Excellent videos.Thanks for sharing!!! Really excited to see your subscribers are growing.
Wonderful lectures.
Thank you very much. You are a genius.
bro where are questions on LIS & DP on grid?
isko LIS nahi aata.
@@sumantopal558 isko jitna aata hai, utna toh seekh le
@@nikhilraj5115 hum toh college dropout hai... Dukaan pe baithke agle 80 saal nikalne waale hai
@@sumantopal558 ungratefulness ki bhi seema hoti hai
@@sumantopal558 toh dukaan par baith na chupchap!
This question is not wildcard pattern matching, right?
LEETCODE Question Name : Is Susequence (EASY)
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
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)
@aditya_verma plzz..upload wildcard matching problem
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
bool isSubsequence(string s, string t) {
int k=0;int j=0;
for(int i=0; i
we can here just use stack to store string a and iterate from backwards of string b and then check
Thanks for this tutorial
please cover LIS also
I think we can use Two pointer approach, It would be better.
This type of same question is asked in Google Kickstart round a 2022 ...😁
Bhai wildcard pattern matching daal do
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";
well you can also solve this using 2 pointer approach with o(n) tc
that length sirf kaam kar jaega concept was great....i was using printLCS .... nice concept of LCS Range E {0 , min(a,b)} 🥰🫶🥰
plz also share pratice questions on relevant topic.
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
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
more optimised is a two pointer solution O(N)
Agar ye poocha ho ki count the no. Of subsequences of one string s that equals another string t ,then what to do
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.
So, by now we got three approach for the problem: Queues, two pointers, dp.
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
Yes we can do that but that is the naive approach and most probably using that would give you a time limit error(TLE).
@@panavkumar9009 lol how come it will be efficient just a single while loop is needed
We can solve it using stacks with O(n) time
😅 😅 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))
Sir ,you doing great work sir thanks from the core of my heart ❤️❣️ sir
And plz upload the complete playlist of dp sir 🙏🙏
Bhaiya please DP series complete kardo
Lcs is overkill for this. Just do linear search or use hashmap and solve in o(n).
bool isSubsequence(string s, string t) {
int i=0;
for(int j=0;j
Could have been solved with two pointer approach too.
can't we do it with two pointer approach too ?
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
Result = t[n][m]
If(result== min(n,m){
Return true;
}
Else{
Return false;
}
*# 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
can anyone paste the link where i can get this practice problem of Sequence Pattern Matching?
Can't we dont it using 2 pointer technique
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;
}
}
Plz make video on greedy algo also
This particular problem can be solved without dp :
Does anyone know how to solve count palindromic subsequences?
Someone please give the link of the question here
public boolean isSubsequence(String s, String t) {
if(s.length()==0)
return true;
int i=0;
int j=0;
while(i
Sir please upload question related to sequence pattern maching.....
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 !! ✌️❤️
@@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 !! ✌️❤️*
how to find time complexity of these algorithm someone plz help
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
we can solve this with 2 pointer approach
17 SEP 2022
#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
Bro can u please upload the recursive video approach?
I am not able to form the choice diagram.
#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
Bro need series on recursion and backtracking
c++ easy solution below--
int i=0;
for(int j=0;j
nice
@Aditya we will return true even if len(LCS) > len(str1)?? or only if they are equal. I am a little confused with question
LCS str1 se badha nhi ho sakta
Maximum voh equal ho sakta
@@gurnoorsingh2954 LCS wala code send kardo bhai , mera segmentation fault dikha rha
#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
*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
Z = gee nhii hota yha , America nhi h ye 💁
tu !! 😂😂 Aap pdhai pe dhyan de Sir !! doubt ho to pooch lena Whatsapp pe ✌️
Ye question kaha par hai
leetcode.com/problems/is-subsequence/
two pointer approach yaha jayda acha hota
ha but isme DP padh rhe hai hum that's why he is using this approach.
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 ;
}
}
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
please make a playlist on backtracking and recursion
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
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
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]
Leetcode Problem :
leetcode.com/problems/is-subsequence/
i can do this without dp :lol
God coder
What in the f
Can anybody please provide the solution of this question using LCS , It shows segmentation fault in gfg
Question-->
practice.geeksforgeeks.org/problems/check-for-subsequence/0
I tried it using dp, but it gave tle. So used two pointer approach which takes O(N) time and O(1) space.
bool isSubSequence(string A, string B)
{
// code here
int i = 0, j = 0, count = 0;
while(j
@@atharvacodes3705 yes I also did using two pointer but using LCS it gives segmentation fault.
My two-pointer approach:
bool isSubSequence(string A, string B)
{
int m= A.length();
int n= B.length();
int j=0;
for(int i=0; i
@@tekbssync5727 then there must be a small mistake in your dp solution