Check if a given string can be formed using characters of adjacent cells of a Matrix | Function to check if the word exists ; If index exceeds board range ; If the current cell does not contain the required character ; If the cell contains the required character and is the last character of the word required to be matched ; Return true as word is found ; Mark cell visited ; Check Adjacent cells for the next character ; Restore cell value ; Driver Code
def checkWord ( board , word , index , row , col ) : NEW_LINE INDENT if ( row < 0 or col < 0 or row >= len ( board ) or col >= len ( board [ 0 ] ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( board [ row ] [ col ] != word [ index ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT elif ( index == len ( word ) - 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT temp = board [ row ] [ col ] NEW_LINE board [ row ] [ col ] = ' * ' NEW_LINE if ( checkWord ( board , word , index + 1 , row + 1 , col ) or checkWord ( board , word , index + 1 , row - 1 , col ) or checkWord ( board , word , index + 1 , row , col + 1 ) or checkWord ( board , word , index + 1 , row , col - 1 ) ) : NEW_LINE INDENT board [ row ] [ col ] = temp NEW_LINE return True NEW_LINE DEDENT board [ row ] [ col ] = temp NEW_LINE return False NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT board = [ [ ' A ' , ' B ' , ' C ' , ' E ' ] , [ ' S ' , ' F ' , ' C ' , ' S ' ] , [ ' A ' , ' D ' , ' E ' , ' E ' ] ] NEW_LINE word = " CFDASABCESEE " NEW_LINE f = 0 NEW_LINE for i in range ( len ( board ) ) : NEW_LINE INDENT for j in range ( len ( board [ 0 ] ) ) : NEW_LINE INDENT if ( board [ i ] [ j ] == word [ 0 ] and checkWord ( board , word , 0 , i , j ) ) : NEW_LINE INDENT print ( " True " ) NEW_LINE f = 1 NEW_LINE break NEW_LINE DEDENT DEDENT if f == 1 : NEW_LINE break NEW_LINE DEDENT if f == 0 : NEW_LINE print ( " False " ) NEW_LINE DEDENT