How to solve using dp

#1

i solved this question without using dp. please tell how to use dp in it. here is my code

#2

@Akshita99
To approach using dp, you will have to create a 2-D dp. In the dp matrix, state (i, j) will be 1 if the string a from index i can be matched to pattern b from index j and 0 otherwise. You will be using a recursive approach. If you arrive at a state (i, j) and the character in the pattern is not ? and *, then if they are equal, you move onto the state (i + 1, j + 1) else you store 0 for the corresponding state and return 0.

If character is ?, you move to the state (i + 1, j + 1) because ? matches one character. If character in pattern is *, then the answer for the state would be (i + 1, j) || (i, j + 1) because * can refer to a sequence of arbitrary length(even an empty sequence).

Try implementing it and revert back if you face any issues.

#3

can it be done with bottom up dp also?

#4

https://ide.codingblocks.com/s/324446 please check what i am doing wrong

#5

only testcase 4 is not running

#6

@Akshita99
Refer to this code.

There were certain errors in your code.

  1. First check if i > ls and j > lp at the same time. Here, you can return 1 as is is confirmed that the string matches the pattern.

  2. When i > ls, you need to check if the rest of the string of the pattern is ‘*’ because otherwise you cannot match an empty string because you have exhausted the entire string at this point.

  3. I have written this piece of code in your code:
    if(pat[j-1]==’?’ || s[i-1]==pat[j-1])
    {

     return um[d] = pattern(s,pat,ls,lp,i+1,j+1); //call for next values
 //return 1 as till here it is satisfied

    }

dp[i][j] means that the string from index i and pattern from index j match with each other. Hence as you first did, we directly cannot set dp[i][j] to 1. We need to analyse the rest of the portions and then conclude.

I also used a map of pairs in this implementation because a 2-D array wasnt able to suffice.

If my solution is able to clear your query, please mark the doubt as resolved.