Coding Interview Question | Wildcard Matching | Dynamic Programming with Optimization

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

[rabindrapatra]

Strange how did you came up with this solution, what is the intention behind this matrix.

[neutralviews]

Thank you very much, got to know how from recursive approach getting to DP approach

[aatifnazar]

dp should be explained in this manner - recursive + memoization

[hiteshgupta]

One of the best explanation I have ever seen. Thank you for the video.

[HarshGangwar]

Can u plz explain 'Super Washing Machines' problem of Leetcode?

[reyazahmed]

Good explanation... I was looking for the initial conditions after watching Tushar video.

[aatifnazar]

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<m; i++)
Arrays.fill(dp[i], -1);

if(isMatchHelper(A, B, 0, 0, dp) == 1)
return true;
return false;
}

public static int isMatchHelper(String A, String B, int i, int j, int dp[][])
{
//base cases
if(i == A.length())
{
for(int k=j; k<B.length(); k++)
{
if(B.charAt(k) != '*')
0;
}
return 1;
}

if(j == B.length())
return 0;

if(dp[i][j] != -1)
return dp[i][j];

int val = 0;
char a = A.charAt(i);
char b = B.charAt(j);

if(a == b || b == '?')
val = 1 & isMatchHelper(A, B, i+1, j+1, dp);
else if(a != b && b != '?' && b != '*')
val = 0;
else if(b == '*')
val = isMatchHelper(A, B, i+1, j, dp) | isMatchHelper(A, B, i, j+1, dp);

dp[i][j] = val;
return val;
}
}

[ravitiwari]

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!!!

[jaggis]

Nice explanation! Please use more space on the white board!

[shalinifefar]

Great explanation. Thank you.
Keep up the good work. 👍

[prajwalgadad]

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.

[manavgarg]

for * case it should be i-2 because if we consider empty b* get disappeared. Please correct if i am worng.

[arihantpatil]

Didn't understand why asterisk could check the upper box value?

[jarjarbinks]

I mean why not use the greedy approach? It is better in both space & time complexity than DP

[theshauryasinghofficial]

@4:35 why strings are represented vertically and patterns horizontally

[sriramphysics]

wroth watching 20 minutes well done Keerti

[krishnakanthd]

Thank you for the detailed explanation :)

[naveennoel]

It went inside my head very well!! Thank you Keerti 🤗

[suchanachakrabarti]

Thank you for the video, your explanations are awesome!!

[rachitagrawal]

Nice explanation of the initial conditions as I found it is the most tricky part.