# O(N.P) solution to Wildcard matching

• Dynamic Programming formulation is as follows.

The Sub-problem is:
T(i,j) = True if string s_1,s_2,s_3,…s_i matches pattern p_1,p_2,p_3,…p_j

The Recurrence Relation is:
If p_j is ‘*’:

• T(i,j) = T(k,j-1) for some k <= i, upto which a match has been performed

Elif p_j is ‘?’:

• T(i,j) = T(i-1,j-1)

Else:

• T(i,j) = T(i-1,j-1) ∧ ( s_i==p_j )

Preconditioned on:
T(0,0)=True
T(i,0)=False for i>0
T(0,j)=True if p_j =="*" else False for j>0

Pseudo-code:

``````Preconditioned T:
T(0,0)=True
T(i,0)=False for i>0
T(0,j)=True if p_j =="*" else False for j>0

isPreconditioned T(i,j)
return True if (i≥0∧j=0)∨(i=0∧j≥0) 	// Checks for pre-conditions

For i in 1->N
For j in 1->P
If not Preconditioned T(i,j)	// Can’t change preconditions
If p_j =="*" and p_(j-1) !="*":
T(i,j) = True if for any k<=i, there is T[k,j-1]=True // Note: see below
elif p_j == "*" and p_(j-1)  == "*":	// Just copy the column
T(i,j)=T(i,j-1)
elif p_j is "?":
T(i,j) = T(i-1,j-1)
Else:
T(i,j) = T(i-1,j-1) ∧(s_i=p_j)
``````

Note:
In order to avoid looping over every k<=i, it is possible to keep track of column j-1 as shown in code below. Runtime achieved = O(N.P) where N: string length, P: pattern length

``````def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
if len(s)==0 and len(p)==0: return True
elif len(s)==0 and len(p)==1 and p[0]=='*': return True
elif len(s)>0 and len(p)==0: return False
# s=[i for i in s]
# p=[i for i in p]
N=len(s)
P=len(p)
s = '_' + s
p = '_' + p

T=[[-1]*(P + 1) for i in range((N + 1))]
track_star=[[-1]*(P + 1) for i in range((N + 1))]
T[0][0], track_star[0][0] = 1, 1
for i in range(1,N+1):
T[i][0] = 0
for j in range(1, P + 1):
if p[j] == '*': T[0][j], track_star[0][j] = T[0][j - 1], track_star[0][j-1]
else:           T[0][j] = 0
isPreconditioned = lambda i, j: True if ((i >= 0 and j == 0) or (i == 0 and j >= 0)) else False
for i in range(1, N + 1):
for j in range(1, P + 1):
if not isPreconditioned(i, j):

if p[j] == '*' and p[j - 1] != '*':
flg = True if track_star[i-1][j-1]==1 or T[i][j-1]==1 else False
if flg: T[i][j], track_star[i][j-1] = 1, 1
else:   T[i][j]=0

elif p[j] == '*' and p[j - 1] == '*':
T[i][j] = T[i][j - 1]
track_star[i][j-1]=track_star[i][max(0,j-2)]

elif p[j] == '?':
T[i][j] = T[i - 1][j - 1]

else:
if T[i - 1][j - 1] == 1 and s[i] == p[j]:
T[i][j] = 1
else:
T[i][j] = 0

return T[N][P]==1
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.