Wildcard Matching Dynamic Programming | Leetcode Hard Solutions
Вставка
- Опубліковано 25 сер 2024
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the solution for the Wildcard Pattern Matching problem using Dynamic Programming in JAVA. In this problem,
1. You are given two strings S1 and S2. S1 represents a text and S2 represents a wildcard pattern.
2. You have to print 'true' if the wildcard pattern is matched with the given text, otherwise print 'false'.
The wildcard pattern can include the characters '?' and '*'
'?' - matches any single character
'*' - matches any sequence of characters (including the empty sequence).
To attempt and submit this question, click here: www.pepcoding....
For a better experience and more exercises, VISIT: www.pepcoding....
#dynamicprogramming #leetcode
Have a look at our result: www.pepcoding....
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
This question has been explained by many honestly, but in every explanation they just start with DP, this is the ONLY tutorial that explains it step by step. why DP? How DP? and most importantly the formula is derived by understanding and not just asked to mug up. Crisp and brilliant explanation.
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
but striver said he will explain all three approaches i.e. top down, bottom up and space optimised dp. Sir do you think he is the best?
@@ShashankRustagiCSE best vo h jiska tumhe smj aye
This is the best explanation of this question on the internet, especially the explanation of the optimisation in '*'.
Thankyou beta!
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Keep learning and keep loving Pepcoding😊
Can someone also provide the solution for top down approach for this question
Sir, I have watched most of the leetcode hard type questions from your channel, you are really doing a great job. Thanks for providing this content for free.
Thankyou beta!
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review - g.page/Pepcoding/review?rc
@@Pepcoding Done :)
Can someone also provide the solution for top down approach for this question
Impressed how you taught! I was looking for bottomup speacially for star character. I understood it because of you :)
Sir wo baat hai na jo teacher log bolte hain ki " beta jitni baar puchhoge utni baar samjhaaunga" , sir aap uske EPITOME ho. Aapni itni baar ek hi baat dohrai hi na ki, koi student samjhe bina rehe hi nhi sakta. Thank u so much sir, respect++ && as usual "EAST HO YA WEST SUMEET SIR IS THE BEST".
Thank you for appreciating. keep motivating, keep learning and keep loving Pepcoding😊
Best explanation Sir, Jab iska code GFG pe dekha toh laga keyboard tod du, ab aisa lag raha h ek do aur khareed lu.
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
ua-cam.com/users/Pepcodingabout?view_as=subscriber
For clearing your doubts, you can join our community on telegram
t.me/pepcoding
epic comment i had seen ever.
LMAO ded
Wonderful!! Never thought the solution to this question could be explained so clearly. Everywhere on the net we find just code with no explanation or reasoning, but not in your channel. Thanks!!
Can someone also provide the solution for top down approach for this question??
This is the best explanation for this problem.
This man is using all his energy to explain the "why" of the solution of this problem!
Thank you so so so so so much sir!
I watched till the end!
Highly underrated channel , truly deserve much !
One of the best explanation so far. This channel needs to be on the top for best coding tutorials(Especially for DP).
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
Can someone also provide the solution for top down approach for this question??
Your way of teaching is really appreciating.It becomes very easy to understand.Happy Teachers Day to such a awesome teacher
100% agree to what Seemant said, i love how Sumeet sir explains things, making logic so simple to implement. These videos are now becoming my normal timepass, when i get bored i open youtube and watch pepcoding, nostalgic, i am getting addicted to DS now :)
We are really glad that it could be interesting and helpful. For better experience and precisely organised content visit - naods.pepcoding.com
Don't forget to follow us on Instagram instagram.com/pepcoding/
i have never seen this much level of perfectt explaination ❤❤❤❤
I don't think these kind of question can be solved without watching the solutions.
Just a minor correction, i and j should start from dp.length and do[0].length. Please correct me if I am wrong. Btw very nice explanation to detail, loved it!
Correct
Thank you bhai bahut der baad aapka comment dekha tab jake submit huaa 2+ hr. Time barbaad ho gya dry run karne me . Love u bro and thank you so much❤️❤️❤️
His smile at 28:33 says it all. God bless him.
sumit sir hum to aapke fan ho gaye.... Thanku for such insightful explaination.. best explaination on the internet for the problem....
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
ua-cam.com/users/Pepcodingabout?view_as=subscriber
Sir with the help of your explanation now i can able to solve the hard problems of dp
thankyou so much sir
If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Can someone also provide the solution for top down approach for this question??
sir iss quetion mei apne quatle aam macha diya , maza aagya. bhaisab.
Thankyou beta!
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Keep learning and keep loving Pepcoding😊
Cannot be explain in any better way than this !! Thank you.
Glad it was helpful! and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Bahi wahh.. HATS OFF to you, the way you explained this prob. and optimization.. Next level... Feeling lucky that I can match your language preference also.. spending 40 mins in this lecture (worst case 2*40 mins for a revisit) would be better that better than looking other videos that has shorter duration. Of course vide time complexity matters a lot but can be ignored at the cost of getting clarity on solution.
I Can't Thank You Enough! This Is The Best Channel For DSA Videos!
Thank You So Much Man!
Great explanation bro,
For the optimization part for the star I tried something else which worked and my solution got accepted.
My optimization:
store the variable of the first true column (rightmost in this case, since we'll be traversing from right) in the immediate lower row, let's say the variable is last_true_column. So for any column with star in the current row, we'll check if that column is less than or equal to last_true_column or not, if yes we'll put True, False otherwise.
Nice 😀
Very good explanation..solution could reach more people if you could explain it in English.
Generalize where the concept of DP is used, (i mean not the overlapping problems )
wildcard Matching , Knapsack problem, no of ways in grid, etc like this make a video on listing out how different problems can be solved using Dynamic Programming. (List out all problems that can be solved with DP concept..^
Best ever explaination💯🔥
Amazing explanation sir! Thank you so much for making these hard questions easy!!
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
class Solution:
def isMatch(self, s: str, p: str) -> bool:
dp = [[None for _ in range(len(s)+1)] for k in range(len(p)+1)]
for i in range(len(dp)-1,-1,-1):
for j in range(len(dp[0])-1,-1,-1):
if i == len(dp)-1 and j == len(dp[0])-1:
dp[i][j] = True
# elif i == len(dp)-1 and p[i] == "*":
# dp[i][j] = True
elif i == len(dp)-1:
dp[i][j] = False
elif j == len(dp[0])-1:
if p[i] == "*":
dp[i][j] = dp[i+1][j]
else:
dp[i][j] = False
else:
if p[i] == "?":
dp[i][j] == dp[i+1][j+1]
elif p[i] == "*":
dp[i][j] == dp[i+1][j] or dp[i][j+1]
elif p[i] == s[j]:
dp[i][j] = dp[i+1][j+1]
else:
dp[i][j] = False
return dp[0][0]
i am getting wrong answer in the "or" step.Please Help
very elegant explanation although i am a big fan of recursive solution but i will pass this tabulation solution.
Best best and the very best expalnation
very good explanation sir
Superb Explanation
Sir jab koi new problem solve kare dp ki , to ye andaaz kaise lagae ki bottom right se bhare ya fir top left se. ??
lajawab optimisation sirji.
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
cant be more thankful
How can he explain so well? Too good
How is he putting blank position at the end now? Any idea?
Thank you so much beta
The best explanation one can get.
Kaise sochate ho kaisa🤯👌👌
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Amazing explanation sir!
If I am stuck on a question and I see you have a video on it , I can be sure that I wont require any other video's explanation.
legend!!
🙏🙏
kamaal ho paaji tussi ♥
sir... aap mahan hooo
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
Best line,
* ne 'a' ko kha liya tab bhi zinda hai 😂
nice explaination sir 👏
😂
* harami hai
Not a single dislike... Hatts off to you sir. Awesome explaination
Do aa gaye bhai ab🥺 kaun hain ye log, kahan se aate hain ye
@@shang_chi4651 insaan h ye log or apne-apne gharo se aate hai
@@anshsarin19 😅 par dislike kyun karke jaate🥺
Thanks for everything you doing sir
My pleasure.
For better experience and well organised content sign up on nados.io
And for being updated follow us on Instagram instagram.com/pepcoding/
Concept clear👌👌....
awesome explanation sir
Thankyou beta, I hope that you are watching till the end and trying to understand the what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Nice explanation sirji
Please visit nados.pepcoding.com for more detailed and curated content on DSA, Web Dev etc for free
best explanation
Best explanation on the internet!
Glad you liked it.
Keep learning.
And for better experience and well organised content explore nados.pepcoding.com
Vera Level Bro very clear Thank you so much...................
what an explanation, thanks a lot....
Glad it was helpful and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
as the dp is of boolean type, how can it be assigned to int i as type mismatch is there. please explain. your code is not running in c++
Great explanation
Glad you liked it!
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
Thanks alot sir 🙏🙏
Best of best...🙏🙏🙏
Thankyou beta for being our constant supporter😊
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
superb explanation sir..Sir can please make a series from cses problem set on graph and tress ,Coz there is none of them have done clear cut playlist on them
Sir video ekdum smjh agyi, bas ek suggestion hai ki ise top to bottom krwaie, bcus wo zyada easy hota hai undersstand krne mei , ulta loop zyada confusing lagta hai ! :)
next top to bottom karwai hai
I think for dp[i][j] shouldn't we consider p[i-1] and s[i-1] because dp[i][j] will tell us i size and j size of s and p respectively instead of indexes
what a effort .....hats off
thank you
@@Pepcoding i should say .... this every day to u
Very Nice Explanation........Keep making videos
Thank you, I will
Can't we take blank space at the 0th index ?
maja aa gya ❤❤🔥🔥
great video.. pls also upload video on leet code #10. Regular Expression Matching
done. please check out the latest video.
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
@@Pepcoding Thank you sir!!
Best explanation
Glad you think so! and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
as always only one word. Awesome :-)
Thank you so much.
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
best explanation!(especially for that * part)
Glad you think so!
If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Can someone also provide the solution for top down approach for this question??
Gratitude!
Awesome!
i think there was a small mistake i should start from dp.length not from dp.length-1 similarlly j and trivial cases also changes to i == dp.length and j == dp[0].length
ya I think so
@@sanmeetwakchaure8530 No. Iteration starts from the bottom right cell which is dp.size()-1.
@@shubhamsood1406 yes. Got it. Thanks😊
thanks bhaiya mai to string ko leke soch he nhi raha tha ......akele char leke krta gaya 6 ghnata nikalgaya.
Haha..koi nh beta, atleast you tried to find an approach.
Keep learning and keep growing!😊
true teacher. wow
Thank you very much sir
can you solve this top down?
Woooooooooooooooooooooooooow
Best !!!
sir its a very humble request ...please sir is topic k baad sliding window technique se releated videos bna dijiyega ...kaafi problem aati h usme..and thankyou for this content sir
Ji jaroor dalenge.
Why it isnt running in interview bit
thank you so much sir for all these, m thoda slow hu😅
Keep it up
Can someone also provide the solution for top down approach for this question??
when s="aa";
p="*"
then it give wrong answer plz help
awesome explaination
keep motivating, keep learning and keep loving Pepcoding😊
Thankyou sir😁
Sir is it necessary to add blanks in dp table?
no, it is to make it easy for us.
@@Pepcoding thank you sir for your quick reply
Maybe once in a generation teacher he is
Sir, why in this particular problem you have kept blank string at the end of the matrix and not at the start like any other dp problem. Can you please explain this?
LCS aur is problem mein sir ne aise hi last mein rakh diya blank, aiss koi compulsory nhi hai. Bas meaning assign karna aana chahiye cells ko
error when s=aa and p=*
Sir, can we do it using top down approach, as we do in lcs,..any specific reason to use bottom up?
Have you got solution for this?
respect ++..♾️
Thanks :) Visit nados.pepcoding.com for more videos like this
💯💯👏👏
❤️❤️❤️
sir can we do al kinds of dp problems in top down and bottom up approach or it depends on the question
You can do them any way but comparatively bottom up apporach is easier to think.
Sir aapke hisab se iski bruteforce approach kya hogi ? Backtracking se bhi ho sakta hai na ye question?
sare dp questions recursion se ho jate hain. Iska formula he recursion ki calls mei dikhega.
Thanku sir
31:55 ( my mind : in dono ka or ind ono ka or indono ka or oh indore )
sir, last column direct he false kar du ??????????
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
We can't do it direct coz there is a chance pattern can contain '*' in which case we have to check dp[i+1][n] value (treating * as a null)
Sir college ke final year exams aa gye , 2 hafte ka break lena padega, ds ke alawa kuch aur karne ka man hi nhi karta, nevertheless will resume learning after 2 weeks.
College padhne nahi deta.
@@Pepcoding Facts
@@Pepcoding pata nhi sir curriculum kyun banaya gaya hai, jab ds algo, os, oops aur dbms hi important hai to electronics je subjects kyun padhate hain.🙄
@@shang_chi4651 electronics? That's shit subject 1001 blah blah
Sir I want to make some java library as an some mini project for e.g to create your own library for Linked list or graph or any data structure .
Pls help sir ho sake to ek video bna do sir Esme kyoki bahut kaam time me ek decent project bn skta hai resume ke liye ya ......
Pls reply sir
ok ji, i will think.
Sir I am 2020 passout . Want to get job in product based company . Is their course which I join to get good job..
yes, try our levelup or IP course. contact 01140194461.
@@Pepcoding sir one question in product based 12 class percentage matters a lot or only required btech cgpa..