How to find validity of a string of parentheses, curly brackets and square brackets?

Question

I recently came in contact with this interesting problem. You are given a string containing just the characters '(', ')', '{', '}', '[' and ']', for example, "[{()}]", you need to write a function which will check validity of such an input string, function may be like this:
bool isValid(char* s);
these brackets have to close in the correct order, for example "()" and "()[]{}" are all valid but "(]", "([)]" and "{{{{" are not!

I came out with following O(n) time and O(n) space complexity solution, which works fine:

1. Maintain a stack of characters.
2. Whenever you find opening braces '(', '{' OR '[' push it on the stack.
3. Whenever you find closing braces ')', '}' OR ']' , check if top of stack is corresponding opening bracket, if yes, then pop the stack, else break the loop and return false.
4. Repeat steps 2 - 3 until end of the string.

This works, but can we optimize it for space, may be constant extra space, I understand that time complexity cannot be less than O(n) as we have to look at every character.

So my question is can we solve this problem in O(1) space?

Answer 1

I doubt you'll find a better solution, since even if you use internal functions to regexp or count occurrences, they still have a O(...) cost. I'd say your solution is the best :)

To optimize for space you could do some run-length encoding on your stack, but I doubt it would gain you very much, except in cases like {{{{{{{{{{}}}}}}}}}}.

Answer 2

You can only reduce the space complexity to O(n/2) as you always expect to have pairs of braces and abort if you reached that bound. But that’s still O(n).

Answer 3

CORRECTION.... I am wrong. :) I will leave my answer as an exercise to the reader as to why it will not work.

Given the problem parameters, I believe the negative case can be broken down into 2 failures:

1) There is a closing brace immediately after an opening brace of a different type.
2) The number of opening braces of any type is not equal to the number of closing braces.

With that in mind you could write the following function (pseudo-code):

function isValid(string) {
    lastOpen = -1;  // Not null, as this catches the case where the first character
                    // is a closing brace.

    for(i=0; i<string.length; i++) {
         char = string.charAt(i);

         // Increment count on opening brace, decrement on close
         // and keep track of the last opening brace
         if(openingBrace) {
             parenCount[braceType] ++;  //Where braceType is an enum of reg, curly, square
             lastOpen = braceType;
         } else {
             // If the last opening brace does not match the next closing => fail
             if(lastOpen != null && lastOpen != braceType) { 
                 return false; 
             }
             lastOpen = null;
             parenCount[braceType] --;  //Where type is an enum of reg, curly, square
         }

    }

    // If parens are not balanced in number => fail
    for(j=0; j<parenCount.length; j++) {
        if(parenCount[j] != 0) {
            return false;
        }
    }

    return true;
}

I think that would work, and is O(1) space.

Answer 4

Actually, there's a deterministic log-space algorithm due to Ritchie and Springsteel: http://dx.doi.org/10.1016/S0019-9958(72)90205-7 (paywalled, sorry not online). Since we need log bits to index the string, this is space-optimal.

---

If you're willing to accept one-sided error, then there's an algorithm that uses n polylog(n) time and polylog(n) space: http://www.eccc.uni-trier.de/report/2009/119/

Answer 5

If the input is read-only, I don't think we can do O(1) space. It is a well known fact that any O(1) space decidable language is regular (i.e writeable as a regular expression). The set of strings you have is not a regular language.

Of course, this is about a Turing Machine. I would expect it to be true for fixed word RAM machines too.

Answer 6

If you can overwrite the input string (not reasonable in the use cases I envision, but what the heck...) you can do it in constant space, though I believe the time requirement goes up to O(n²).

Like this:

string s = input
char c = null
int i=0
do
  if s[i] isAOpenChar()
    c = s[i]
  else if
    c = isACloseChar()
      if closeMatchesOpen(s[i],c)
         erase s[i]
         while s[--i] != c ;
         erase s[i]
         c == null
         i = 0;      // Not optimal! It would be better to back up until you find an opening character
      else 
         return fail
  end if
while (s[++i] != EOS)
if c==null
  return pass
else
  return fail

The essence of this is to use the early part of the input as the stack.

Answer 7

I have a simple, though perhaps erroneous idea, that I will submit to your criticisms.

It's a destructive algorithm, which means that if you ever need the string it would not help (since you would need to copy it down).

Otherwise, the algorithm work with a simple index within the current string.

The idea is to remove pairs one after the others:

1. ([{}()])
2. ([()])
3. ([])
4. ()
5. empty -> OK

It is based on the simple fact that if we have matching pairs, then at least one is of the form () without any pair character in between.

Algorithm:

1. i := 0
2. Find a matching pair from i. If none is found, then the string is not valid. If one is found, let i be the index of the first character.
3. Remove [i:i+1] from the string
4. If i is at the end of the string, and the string is not empty, it's a failure.
5. If [i-1:i] is a matching pair, i := i-1 and back to 3.
6. Else, back to 1.

The algorithm is O(n) in complexity because:

• each iteration of the loop removes 2 characters from the string
• the step 2., which is linear, is naturally bound (i cannot grow indefinitely)

And it's O(1) in space because only the index is required.

Of course, if you can't afford to destroy the string, then you'll have to copy it, and that's O(n) in space so no real benefit there!

Unless, of course, I am deeply mistaken somewhere... and perhaps someone could use the original idea (there is a pair somewhere) to better effect.