Dynamic Programming | Wildcard Pattern Matching | Linear Time and Constant Space | Function that matches input text with given wildcard pattern ; empty pattern can only match with empty string . Base Case : ; step - 1 : initialize markers : ; For step - ( 2 , 5 ) ; For step - ( 3 ) ; For step - ( 4 ) ; For step - ( 5 ) ; For step - ( 6 ) ; For step - ( 7 ) ; Final Check ; Driver code
function strmatch ( txt , pat , n , m ) { if ( m == 0 ) return ( n == 0 ) ; let i = 0 , j = 0 , index_txt = - 1 , index_pat = - 1 ; while ( i < n ) { if ( j < m && txt [ i ] == pat [ j ] ) { i ++ ; j ++ ; } else if ( j < m && pat [ j ] == ' ' ) { i ++ ; j ++ ; } else if ( j < m && pat [ j ] == ' ' ) { index_txt = i ; index_pat = j ; j ++ ; } else if ( index_pat != - 1 ) { j = index_pat + 1 ; i = index_txt + 1 ; index_txt ++ ; } else { return false ; } } while ( j < m && pat [ j ] == ' ' ) { j ++ ; } if ( j == m ) { return true ; } return false ; } let str = " " . split ( ' ' ) ; let pattern = " " . split ( ' ' ) ; if ( strmatch ( str , pattern , str . length , pattern . length ) ) document . write ( " " + " " ) ; else document . write ( " " + " " ) ; let pattern2 = " " . split ( ' ' ) ; if ( strmatch ( str , pattern2 , str . length , pattern2 . length ) ) document . write ( " " + " " ) ; else document . write ( " " ) ;