Solution in C


  • 0
    D

    By creating stack structure to push left-bracket whenever a '{', '[', or'(' appears, and check the balancing, matched right-bracket before pop its left-side partner, we can check any illegal usage of bracket pairs. This method, though simple, is still a Theta(n) linear one.

    typedef struct BRACKET {
    /* create singly linked list for implementing stack */
        char ch;
        struct BRACKET *next;
    } Bracket;
    
    Bracket *bracket_stack;
    char Top( void );
    void Push( char ch );
    void Pop( void );
    int isEmpty( void );
    void createStack( void );
    
    char Top( void ) {
        return bracket_stack->ch;
    }
    
    void Push( char ch ) {
        Bracket *head;
        head = (Bracket *)malloc( sizeof( Bracket ) );
        assert( head != NULL );
        
        head->ch = ch;
        head->next = bracket_stack;
        bracket_stack = head;
    }
    
    void Pop( void ) {
        if( !isEmpty() ) {
            Bracket *temp = bracket_stack;
            bracket_stack = bracket_stack->next;
            free( temp );
            temp = NULL;
        }
    }
    
    int isEmpty( void ) {
        return ( Top() == 'r' ? 1 : 0 );
    }
    
    void createStack( void ) {
        bracket_stack = (Bracket *)malloc( sizeof( Bracket ) );
        assert( bracket_stack != NULL );
        
        bracket_stack->ch = 'r';
        bracket_stack->next = NULL;
    }
    
    bool isValid(char* s) {
        char ch;
        createStack();
        
        while( ( ch = *s++ ) != '\0' ) {
            switch( ch ) {
                case '(':
                case '[':
                case '{':
                    Push( ch );
                    break;
                case ')':
                    if( !isEmpty() && Top() == '(' )
                        Pop();
                    else
                        return 0;
                    break;
                case ']':
                    if( !isEmpty() && Top() == '[' )
                        Pop();
                    else
                        return 0;
                    break;
                case '}':
                    if( !isEmpty() && Top() == '{' )
                        Pop();
                    else
                        return 0;
                    break;
            }   
        }
        
        return isEmpty();
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.