C solution (0ms) using realloc to simulate stack/dynamic array


  • 0

    A lot of C programmers resort to implementing a linked list based stack to solve this problem. However, we can easily solve it using a realloc based dynamic array, which saves you time in an interview setting.

    #define resize(stack, len) (stack = realloc(stack, len * sizeof(char)))
    
    bool isValid(char* s) {
        int stackSize = 0;
        char *stack = NULL, top;
        while (*s) {
            if (*s == '{' || *s == '[' || *s == '(') {
                resize(stack, ++stackSize);
                stack[stackSize - 1] = *(s++);
                continue;
            }
            if (stackSize == 0) return false;
            top = stack[stackSize - 1];
    
            switch (*s) {
                case '}': if (top != '{') return false; break;
                case ']': if (top != '[') return false; break;
                case ')': if (top != '(') return false; break;
                default: return false;
            }
            resize(stack, --stackSize);
            s++;
        }
        return stackSize == 0;
    }
    

Log in to reply
 

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