# Problem Statement :

The wildcard pattern can include the characters ‘?’ and ‘*’

‘?’ — matches any single character

‘*’– Matches any sequence of characters (sequence can be of length 0 or more)

Sample Input:

`wildcard pattern = ?aytext = ray`

Sample Output:

`True`

# Iterative DP

Create a N*M dimensional array DP where N is the size of the text and M is the size of the pattern string.

Let’s take care of base cases first.

• DP = 1 // Because if text and pattern are empty strings they matches.
• DP[i] = 0 // Because if the size of the pattern is 0 then any length of the text will not match with the pattern except 0 length text.
• DP[j] = DP[j-1] when the j’th character is ‘*’.

Now run two loop first from i = 1 to i = N and second loop from j = 1 to j = M and we will use same recursive relation here i.e

1. If TEXT[i-1] == PATTERN[j-1] or PATTERN[j-1]==’?’
• DP[i][j]=DP[i-1][j-1]
• That is if the current characters matches then our answer will be whatever the answer was for one length smaller text and 1 length smaller pattern.

2. If PATTERN[j-1]=’*’

• DP[i][j] = DP[i — 1][j] or DP[i][j — 1] or DP[i — 1][j — 1];
• ‘*’ can match 0 or more characters so we will have three option here.

3. Otherwise

• DP[i][j]=0
• That is the current characters do not match.

Now our answer is at DP[N][M] so return the value at DP[N][M].

Time Complexity : O(N*M)
Space Complexity : O(N*M)