algorithm - 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:

([)]
{()[}]