Solution in C


  • 0
    L

    Intuition

    Iterate through the string, use 3 integers to count the number of '(' , '[', and '{', when it comes to ')', ']' and '}', reduce the interger respectively. At the end of the algorithm, if the 3 integers equal zero, it means that the string is valid.

    Algorithm

    1. If the length is zero or odd, it means the string is nonvalid.
    2. Iterate through the string, when it comes to '(' , '[', or '{' , the corresponding integer increase by 1, and push the left bracket into stack, when it comes to ')', ']', or '}', if it matches the bracket in stack, then pop stack and reduce the corresponding integer. If it dosent match, it means the sring is non valid.
    3. After Iterating through the string, if the 3 integers equal zero, it means that the string is valid.
    bool isValid(char* s) {
        int len = strlen(s);
        if(len == 0 || len % 2 != 0){
            return false;
        }
        int count0 = 0; //()
        int count1 = 0; //[]
        int count2 = 0; //{}
        char *stack = (char *)malloc(sizeof(char) * len);
        int idx = 0;
        int i = 0;
        int ptr = 0;
        while(s[idx] != '\0'){
            if(s[idx] == '('){
                count0++;
                stack[i++] = '(';
                ptr = i - 1;
            }else if(s[idx] == '['){
                count1++;
                stack[i++] = '[';
                ptr = i - 1;
            }else if(s[idx] == '{'){
                count2++;
                stack[i++] = '{';
                ptr = i - 1;
            }else if(s[idx] == ')'){
                if(stack[ptr] == '('){
                    count0--;
                    i = i - 1;
                    ptr = i - 1;
                }else{
                    return false;
                }
            }else if(s[idx] == ']'){
                if(stack[ptr] == '['){
                    count1--;
                    i = i - 1;
                    ptr = i - 1;
                }else{
                    return false;
                }
            }else if(s[idx] == '}'){
                if(stack[ptr] == '{'){
                    count2--;
                    i = i - 1;
                    ptr = i - 1;
                }else{
                    return false;
                }
            }
            idx++;
        }
        if(count0!=0 || count1!=0 || count2!=0){
            return false;
        }
        
        free(stack);
        return true;
    }
    

    Complexity Analysis

    • Time complexity: O(n)
    • Space complexity: O(n)

Log in to reply
 

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