Check if a given pattern exists in a given string or not | Java 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
import java . io . * ; class GFG { static boolean isMatch ( String text , String pattern ) { if ( text == null pattern == null ) { return false ; } int N = text . length ( ) ; int M = pattern . length ( ) ; boolean [ ] [ ] dp = new boolean [ N + 1 ] [ M + 1 ] ; dp [ 0 ] [ 0 ] = true ; for ( int i = 0 ; i < M ; i ++ ) { if ( pattern . charAt ( 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 . charAt ( j ) == ' . ' ) { dp [ i + 1 ] [ j + 1 ] = dp [ i ] [ j ] ; } if ( pattern . charAt ( j ) == text . charAt ( i ) ) { dp [ i + 1 ] [ j + 1 ] = dp [ i ] [ j ] ; } if ( pattern . charAt ( j ) == ' * ' ) { if ( pattern . charAt ( j - 1 ) != text . charAt ( i ) && pattern . charAt ( j - 1 ) != ' . ' ) { dp [ i + 1 ] [ j + 1 ] = dp [ i + 1 ] [ j - 1 ] ; } else { dp [ i + 1 ] [ j + 1 ] = ( dp [ i + 1 ] [ j ] dp [ i ] [ j + 1 ] dp [ i + 1 ] [ j - 1 ] ) ; } } } } return dp [ N ] [ M ] ; } public static void main ( String [ ] args ) { String text = " geeksforgeeks " ; String pattern = " ge * ksforgeeks " ; if ( isMatch ( text , pattern ) ) { System . out . println ( " Yes " ) ; } else { System . out . println ( " No " ) ; } } }