Check if a given pattern exists in a given string or not | C ++ program for the above approach ; Function to check if the pattern consisting of ' * ' , ' . ' and lowercase characters matches the text or not ; Base Case ; Stores length of text ; Stores length of pattern ; dp [ i ] [ j ] : Check if { text [ 0 ] , . . text [ i ] } matches { pattern [ 0 ] , ... pattern [ j ] } or not ; Base Case ; Iterate over the characters of the string pattern ; Update dp [ 0 ] [ i + 1 ] ; Iterate over the characters of both the strings ; If current character in the pattern is ' . ' ; Update dp [ i + 1 ] [ j + 1 ] ; If current character in both the strings are equal ; Update dp [ i + 1 ] [ j + 1 ] ; If current character in the pattern is ' * ' ; Update dp [ i + 1 ] [ j + 1 ] ; Update dp [ i + 1 ] [ j + 1 ] ; Return dp [ M ] [ N ] ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int isMatch ( string text , string pattern ) { if ( text == " " or pattern == " " ) return false ; int N = text . size ( ) ; int M = pattern . size ( ) ; vector < vector < bool > > dp ( N + 1 , vector < bool > ( M + 1 , false ) ) ; dp [ 0 ] [ 0 ] = true ; for ( int i = 0 ; i < M ; i ++ ) { if ( pattern [ i ] == ' * ' && dp [ 0 ] [ i - 1 ] ) { dp [ 0 ] [ i + 1 ] = true ; } } for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { if ( pattern [ j ] == ' . ' ) { dp [ i + 1 ] [ j + 1 ] = dp [ i ] [ j ] ; } if ( pattern [ j ] == text [ i ] ) { dp [ i + 1 ] [ j + 1 ] = dp [ i ] [ j ] ; } if ( pattern [ j ] == ' * ' ) { if ( pattern [ j - 1 ] != text [ i ] && pattern [ j - 1 ] != ' . ' ) { dp [ i + 1 ] [ j + 1 ] = dp [ i + 1 ] [ j - 1 ] ; } else { dp [ i + 1 ] [ j + 1 ] = ( dp [ i + 1 ] [ j ] or dp [ i ] [ j + 1 ] or dp [ i + 1 ] [ j - 1 ] ) ; } } } } return dp [ N ] [ M ] ; } int main ( ) { string text = " geeksforgeeks " ; string pattern = " ge * ksforgeeks " ; if ( isMatch ( text , pattern ) ) cout << " Yes " ; else cout << " No " ; }