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:
'('
, '{'
OR '['
push it on the stack.')'
, '}'
OR ']'
, check if top of stack is corresponding opening bracket, if yes, then pop the stack, else break the loop and return false.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?
Push an opening parenthesis on top of the stack. In case of a closing bracket, check if the stack is empty. If not, pop in a closing parenthesis if the top of the stack contains the corresponding opening parenthesis. If the parentheses are valid, then the stack will be empty once the input string finishes.
3. Brackets are used to enclose parenthetical materials within the parentheses while parentheses are used to enclose words, numbers, phrases, sentences, symbols, and other items in a sentence.
Valid Parentheses solution in Java We iterate over the characters of the string, and for every iteration: if the current character is an opening bracket, we push it in the stack. if the character is a closing bracket, we pop the stack and check if the top of the stack contains its corresponding opening bracket or not.
Use Stack , while iterating through each character of the input string , to Push any opening brackets to the stack and to Pop the closing bracket if it matches the closing bracket of the latest opening bracket in the stack . At the end of the iteration, if the stack is empty, then all the brackets were balanced.
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:
([)] {()[}]
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/
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With