Remove Invalid Parentheses | Method checks if character is parenthesis ( openor closed ) ; method returns true if contains valid parenthesis ; method to remove invalid parenthesis ; visit set to ignore already visited ; queue to maintain BFS ; pushing given as starting node into queu ; If answer is found , make level true so that valid of only that level are processed . ; Removing parenthesis from str and pushing into queue , if not visited already ; Driver Code
def isParenthesis ( c ) : NEW_LINE INDENT return ( ( c == ' ( ' ) or ( c == ' ) ' ) ) NEW_LINE DEDENT def isValidString ( str ) : NEW_LINE INDENT cnt = 0 NEW_LINE for i in range ( len ( str ) ) : NEW_LINE INDENT if ( str [ i ] == ' ( ' ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT elif ( str [ i ] == ' ) ' ) : NEW_LINE INDENT cnt -= 1 NEW_LINE DEDENT if ( cnt < 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return ( cnt == 0 ) NEW_LINE DEDENT def removeInvalidParenthesis ( str ) : NEW_LINE INDENT if ( len ( str ) == 0 ) : NEW_LINE INDENT return NEW_LINE DEDENT visit = set ( ) NEW_LINE q = [ ] NEW_LINE temp = 0 NEW_LINE level = 0 NEW_LINE q . append ( str ) NEW_LINE visit . add ( str ) NEW_LINE while ( len ( q ) ) : NEW_LINE INDENT str = q [ 0 ] NEW_LINE q . pop ( ) NEW_LINE if ( isValidString ( str ) ) : NEW_LINE INDENT print ( str ) NEW_LINE level = True NEW_LINE DEDENT if ( level ) : NEW_LINE INDENT continue NEW_LINE DEDENT for i in range ( len ( str ) ) : NEW_LINE INDENT if ( not isParenthesis ( str [ i ] ) ) : NEW_LINE INDENT continue NEW_LINE DEDENT temp = str [ 0 : i ] + str [ i + 1 : ] NEW_LINE if temp not in visit : NEW_LINE INDENT q . append ( temp ) NEW_LINE visit . add ( temp ) NEW_LINE DEDENT DEDENT DEDENT DEDENT expression = " ( ) ( ) ) ( ) " NEW_LINE removeInvalidParenthesis ( expression ) NEW_LINE expression = " ( ) v ) " NEW_LINE removeInvalidParenthesis ( expression ) NEW_LINE