Wildcard Pattern Matching | Function that matches input strr with given wildcard pattern ; empty pattern can only match with empty string ; lookup table for storing results of subproblems ; empty pattern can match with empty string ; Only ' * ' can match with empty string ; fill the table in bottom - up fashion ; Two cases if we see a ' * ' a ) We ignore a * aTM character and move to next character in the pattern , i . e . , a * aTM indicates an empty sequence . b ) ' * ' character matches with ith character in input ; Current characters are considered as matching in two cases ( a ) current character of pattern is ' ? ' ( b ) characters actually match ; If characters don 't match ; Driver code ; char pattern [ ] = " ba * * * * * ab " char pattern [ ] = " ba * ab " char pattern [ ] = " a * ab " char pattern [ ] = " a * * * * * ab " char pattern [ ] = " * a * * * * * ab " char pattern [ ] = " ba * ab * * * * " char pattern [ ] = " * * * * " char pattern [ ] = " * " char pattern [ ] = " aa ? ab " char pattern [ ] = " b * b " char pattern [ ] = " a * a " char pattern [ ] = " baaabab " char pattern [ ] = " ? baaabab " char pattern [ ] = " * baaaba * "
def strrmatch ( strr , pattern , n , m ) : NEW_LINE INDENT if ( m == 0 ) : NEW_LINE INDENT return ( n == 0 ) NEW_LINE DEDENT lookup = [ [ False for i in range ( m + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE lookup [ 0 ] [ 0 ] = True NEW_LINE for j in range ( 1 , m + 1 ) : NEW_LINE INDENT if ( pattern [ j - 1 ] == ' * ' ) : NEW_LINE INDENT lookup [ 0 ] [ j ] = lookup [ 0 ] [ j - 1 ] NEW_LINE DEDENT DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT if ( pattern [ j - 1 ] == ' * ' ) : NEW_LINE INDENT lookup [ i ] [ j ] = lookup [ i ] [ j - 1 ] or lookup [ i - 1 ] [ j ] NEW_LINE DEDENT elif ( pattern [ j - 1 ] == ' ? ' or strr [ i - 1 ] == pattern [ j - 1 ] ) : NEW_LINE INDENT lookup [ i ] [ j ] = lookup [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT lookup [ i ] [ j ] = False NEW_LINE DEDENT DEDENT DEDENT return lookup [ n ] [ m ] NEW_LINE DEDENT strr = " baaabab " NEW_LINE pattern = " * * * * * ba * * * * * ab " NEW_LINE if ( strrmatch ( strr , pattern , len ( strr ) , len ( pattern ) ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT