Simple solution with O(0) memory overhead with pointers.

  • 0

    If the argument is mutable (like in the C and C++ version) you can use it as stack and not allocate any additional memory.
    Just use the beginning of the string as a stack as it is not needed after it is traversed.

    Here is my C solution:

    bool isValid(char* s) {
        char *p, *o = p = s;
        while (*p) {
            if (*p == '(') 
                *(s++) = ')';
            else if (*p == '[')
                *(s++) = ']';
            else if (*p == '{')
                *(s++) = '}';
            else if (s == o || *(--s) != *p)
                return false;
        return s==o;

Log in to reply

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