O(N.P) solution to Wildcard matching


  • 0
    Y

    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
    

Log in to reply
 

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