Coding Interview Question | Wildcard Matching | Dynamic Programming with Optimization
Vložit
- čas přidán 27. 07. 2024
- LeetCode Link - leetcode.com/problems/wildcar...
Video includes following details-
0:00-2:44 - Question explanation with examples
2:44-3:44 - Approach
3:44-4:45 - Visualisation of dp
4:45-7:55 - Initial Conditions
7:55-12:30 - Formation of Algo using examples
12:30-18:30 - Dry run of Algo with explanation
18:30-20:30- Optimizations
Please subscribe to my channel - / keertipurswani
LinkedIn - / keertipurswani
Instagram - keerti.purs...
It went inside my head very well!! Thank you Keerti 🤗
Thanks for such a detailed explanation.
Hey, Thank you so much all your knowledge sharing. I am able to perform very nice in all my interviews. Keep up the good work. More power to you.
Keep rocking!!!
One of the best explanation I have ever seen. Thank you for the video.
Thank you :)
Can u plz explain 'Super Washing Machines' problem of Leetcode?
Thank you for the video, your explanations are awesome!!
I am glad you like them :)
Nice explanation of the initial conditions as I found it is the most tricky part.
@4:35 why strings are represented vertically and patterns horizontally
Good explanation... I was looking for the initial conditions after watching Tushar video.
Excellent explanation for this problem !...i can say this was the final destination for me after roaming through many videos on youtube ... thanks al lot👍
Thank you Naman 😊😊
This is a great explaination
Great explanation !! I have not understood the solution to this problem until I have seen this video, thank you so much for sharing!!!!
Thank you Omar 😊😊
Thank you for such a clear explanation, Keerti!!
Thank you very much, got to know how from recursive approach getting to DP approach
So glad I could explain the basic logic ❤️
Finally, a video I could understand. Thanks a lot for doing this Keerti.
Hope you like other videos as well 😇
@@KeertiPurswani I am going to subscribe to your channel :)
Thank you 😇
Didn't understand why asterisk could check the upper box value?
Great explanation!!! it would be a great help if you make a video on memoization approach.
This is so good!! Thank you!
Strange how did you came up with this solution, what is the intention behind this matrix.
Great explanation. Thank you.
Keep up the good work. 👍
Thank you :)
Thanks for discussing the optimization part!
I now have a separate video on it, check it out and let me know if you like it!
czcams.com/video/7C_FIc7PytA/video.html
for * case it should be i-2 because if we consider empty b* get disappeared. Please correct if i am worng.
Would you be able to show us how to arrive to the subproblem? Also top down approach is more intuitive and then we could come up with bottom up approach from the sub problems being repeated in the top down approach. Here in the above video it leaves us no choice other than memorizing the approach.
Can you please tell me why for initialisation, if the pattern[j] is * then we need to check the previous column?
Watch the part from 5:48 again 🙂
As I said, * can represent an empty string as well. So if pattern was just ****, then it's true for empty string 🙂
I understood the logic finally. Thank you.
you killed it girl! Thanks so much
One of the best explanation i found for this problem! Thank you :)
Thank you so much 🥺🥺
Hope you like rest of the videos as well 😇
Best explanation. I am appreciating dp more after seeing your videos.
Thank you for the detailed explanation :)
Good Going Keerti ...All the Best
mind blowing . I have taken a course on coding ninjas & they didn't explain it well , & then i found ur vedio .Awesome , Great work , Plz make more videos on even more difficult questions. U are superb .
thank you so much!
Thank you very much! This was very helpful.
Glad you liked it 😊😇
Sis please reply.
Could you please explain me project Euler archive 51.
That problem uses wild card string(I think so). So please help me.🙇
Will check it out and let you know
Damn your solutions make these questions appear so simple! Keep posting!
I mean why not use the greedy approach? It is better in both space & time complexity than DP
Good explanation, thanks
Your videos clear some of my basic doubts.
That's my mission accomplished 🙂😇
Great Explanation.
Thanks a lot
Thank you 😇
Great video explanation!
please tell the top down approach..like how to come up with recursive solution and then memoisation.interviers like to see the recursive solution and that is mainly expected.
what u r sharing is last approach bottom up..
@@KeertiPurswani actually all youtubers are solving by same approach like tushar roy..it would be helpful if u talk about top down recursive....thanks :)
I completely get it :) But the main reason is to avoid videos becoming even longer, but if people need it- I will definitely consider making separate videos on Recursive solutions :) Also, I have covered these approaches in LCS video and I can notice that retention of users was lot lesser :)
Thanks for the feedback @ayush raj. This will help me make better videos :)
DP is about two things: 1> How a problem relates to it's subproblem, 2>How not to solve a problem again and again. The second part is generally easy once you have solved few DP problems, you just know how your dp structure will look like. It's the first part which is hard to figure out, and the video explains that very well. Now it's your choice how you want to code it, recursive or bottom up. And if you have really understood, it's not difficult to convert one into another. Also, I am not sure about interviewers like to see and expect recursive solution, again it's about how an individual thinks. My preference is bottom up, as recursion is easy but costly.
Nice explanation! Please use more space on the white board!
Thanks for detailed explanation
But when I was trying to solve the problem in leetcode with this logic , some edge case is missing for *. You may try looking at it
Sure, send the code to me on LinkedIn :)
why not ab*a represent aba...since taking * as an empty sequence makes ab*a = aba right
Amazing explanation here from all
Thanks! 😇😇
Hope you like rest of the videos as well ❤️
dp should be explained in this manner - recursive + memoization
So True !!
These CZcamsrs should learn from Aditya Verma's series on dp !!
@@prateeksinghal630 Lets not discourage man
@@naveennoel9496 This is not to discourage anyone !!
If I was trying to discourage anyone then I would have stated that the video is bad and all the BS !!
I was giving just genuine feedback that dp should be tackled in a progressive manner (recursion + memoization + iterative)
@aatif So true!
Great explaination ma'am!!!!
Thank you 😇😇
great explanation mam
helpful video
Thank you Himanshu :)
mam ..i m not understand pat[j-1] means that a=?........for value j=2
Pat[j-1] is because I have added an extra column in starting. So, in the example pat[0] is 'a' which is at 1st column in matrix (not 0)
@@KeertiPurswani thank u mam....
Best explanation
Very insightful👌🏻
Glad you like it! 🙂
you explain very well
Thanks Kunal :)
wroth watching 20 minutes well done Keerti
really nice explanation.
Thanks Abhay! 😇
nice explanatiom
Is it your own solution? Sis
fantastic explanation
Thank you so much ❤️
Best explanation lol. Don't know why others struggle to explain.
Thank you 🙏🙏😇😇 Hope you like rest of the videos as well!
Very good explanations
Thank you 😇😇
Please do share it with your friends ❤️
Didi please make a video on Regular Expression Matching, Leetcode #10
A qs very hard to understand
So many requests for this one. Will cover for sure! 😇
Awesome video !!!!!!!!!!!!!!!!!!
Thanks Avinash 🥺🥺❤️❤️
Genius!
You are 😊
Very nicely explained. Thanks a lot. Plz make a video on its optimisations too.
You may also solve this very efficiently using Tries if the input/output is in the following format:
Input: List of word strings, List of pattern strings
Output: List of booleans for the pattern strings
1. Add words to trie with a last node as end of word
2. For each pattern use DFS:
2.1 if ? omit the character
2.2 If * look for the next character in the DFS
2.3 If end of word reached, return true
beauty with brain
Hum toh solution ko nahi sirf aapko dekh rahe the...aapke chehre se nazar hi nahi hatt rahi thi😁😁😁
Abe padai likhai pe dhyan do IAS Vias bano desh ko sambhalo 😂
@Naman 😂😂😂😂 🙏🙏🙏
@@KeertiPurswani i love u...
@@KeertiPurswani what u do apart from u tube? R u employed or not
@siwi studios, try checking me out on LinkedIn if you love me 🤭🤭😂😂
Jk. I am a software developer. Currently working at Intuit
I think it fails here S =aa p=*
No it doesn't, did you try running the code? Share it with me
@@KeertiPurswani check S="albmnc" p="*?b*c"
in this, if we make a memoization table then it will get fails in s="a" and p="*?b*c"
for solving this you have to introduce one conditon more
m: m is the length of the pattern
for (int j = 1; j
Ashutosh bisht yeah I got it later
Damm she become SDE 2 with experience of just 2 year & still has some hobbies left #respect 🙌🙌🤐
recursive solution passed all cases on leetcode
class Solution
{
public boolean isMatch(String A, String B)
{
int m = A.length();
int n = B.length();
int dp[][] = new int[m][n];
for(int i=0; i