Algorithm

For every index of string S1, we have different options to match that index with string S2. We can think in terms of string matching paths, as in earlier problems:

Either the characters match already.
Or, if there is a ?, we can explicitly match a single character.
For a *, it can match zero or more characters.

As there is no uniformity in data, the only way is to try all possible ways, which means using recursion.

Steps to form the recursive solution

Compare positions in both strings
Treat one string as the pattern (letters, '?' or '*') and the other as the text. Start from the end and move backwards.
Handle current characters
- Characters match: move back in both strings.
- '?' → matches exactly one character: move back in both.
- '*' →
  - Match empty sequence , move back in pattern.
  - Match one or more characters,move back in text.
- Different letters: no match.
Combine results: If any option leads to a match, the strings match.
Base cases
- Both strings finished : match.
- Pattern finished but text left: no match.
- Text finished but pattern left : match only if all remaining are '*'.

Steps to memoize a recursive solution:

If we draw the recursion tree, we will see that there are overlapping subproblems. In order to convert a recursive solution the following steps will be taken:

Create a dp array of size [n][m]. The size of S1 and S2 are n and m respectively, so the variable i will always lie between ‘0’ and ‘n-1’ and the variable j between ‘0’ and ‘m-1’.
We initialize the dp array to -1.
Whenever we want to find the answer to particular parameters (say f(i,j)), we first check whether the answer is already calculated using the dp array(i.e dp[i][j]!= -1 ). If yes, simply return the value from the dp array.
If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[i][j] to the solution we get.

Code