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

With reference to the excellent answer from Matthieu M., here is an implementation in C# that seems to work beautifully.

/// <summary> /// Checks to see if brackets are well formed. /// Passes "Valid parentheses" challenge on www.codeeval.com, /// which is a programming challenge site much like www.projecteuler.net. /// </summary> /// <param name="input">Input string, consisting of nothing but various types of brackets.</param> /// <returns>True if brackets are well formed, false if not.</returns> static bool IsWellFormedBrackets(string input) {     string previous = "";     while (input.Length != previous.Length)     {         previous = input;         input = input             .Replace("()", String.Empty)             .Replace("[]", String.Empty)             .Replace("{}", String.Empty);                     }     return (input.Length == 0); } 

Essentially, all it does is remove pairs of brackets until there are none left to remove; if there is anything left the brackets are not well formed.

Examples of well formed brackets:

()[] {()[]} 

Example of malformed brackets:

([)] {()[}] 

Answer 2

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/