Check if a word exists in a grid or not | Python3 program to check if the word exists in the grid or not ; Function to check if a word exists in a grid starting from the first match in the grid level : index till which pattern is matched x , y : current position in 2D array ; Pattern matched ; Out of Boundary ; If grid matches with a letter while recursion ; Marking this cell as visited ; finding subpattern in 4 directions ; marking this cell as unvisited again ; else : Not matching then false ; Function to check if the word exists in the grid or not ; if total characters in matrix is less then pattern lenghth ; Traverse in the grid ; If first letter matches , then recur and check ; Driver Code ; Function to check if word exists or not
r = 4 NEW_LINE c = 4 NEW_LINE def findmatch ( mat , pat , x , y , nrow , ncol , level ) : NEW_LINE INDENT l = len ( pat ) NEW_LINE if ( level == l ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( x < 0 or y < 0 or x >= nrow or y >= ncol ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( mat [ x ] [ y ] == pat [ level ] ) : NEW_LINE INDENT temp = mat [ x ] [ y ] NEW_LINE mat [ x ] . replace ( mat [ x ] [ y ] , ' # ' ) NEW_LINE res = ( findmatch ( mat , pat , x - 1 , y , nrow , ncol , level + 1 ) | findmatch ( mat , pat , x + 1 , y , nrow , ncol , level + 1 ) | findmatch ( mat , pat , x , y - 1 , nrow , ncol , level + 1 ) | findmatch ( mat , pat , x , y + 1 , nrow , ncol , level + 1 ) ) NEW_LINE mat [ x ] . replace ( mat [ x ] [ y ] , temp ) NEW_LINE return res NEW_LINE return False NEW_LINE DEDENT DEDENT def checkMatch ( mat , pat , nrow , ncol ) : NEW_LINE INDENT l = len ( pat ) NEW_LINE if ( l > nrow * ncol ) : NEW_LINE INDENT return False NEW_LINE DEDENT for i in range ( nrow ) : NEW_LINE INDENT for j in range ( ncol ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == pat [ 0 ] ) : NEW_LINE INDENT if ( findmatch ( mat , pat , i , j , nrow , ncol , 0 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT DEDENT DEDENT return False NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT grid = [ " axmy " , " bgdf " , " xeet " , " raks " ] NEW_LINE if ( checkMatch ( grid , " geeks " , r , c ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT