Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
This can be further optimized

rahul.dhammy

May 29, 2024

We dont need to iterate the entire string we can return false as soon as we first find the mismatched braces. This means we dont need to check the length of the stack at the end. Please see my solution below:

public bool isValid(string s) { if(s.Length==1) // One char string for sure would not be balanced return false; Dictionary<char,char> closingOpeningBracesPairMap = new Dictionary<char,char>(); closingOpeningBracesPairMap.Add(')','('); closingOpeningBracesPairMap.Add(']','['); closingOpeningBracesPairMap.Add('}','{'); Stack<char> stack = new Stack<char>(); for(int i = 0; i < s.Length; i++) { if(IsOpeningBrace(s[i])) { stack.Push(s[i]); } else { var poppedElement = stack.Pop(); if(poppedElement != closingOpeningBracesPairMap[s[i]]) return false; } } return true; } private bool IsOpeningBrace(char brace) { if(brace == '(' || brace =='[' || brace == '{') return true; else return false; }

0

0

Comments
Comments
Fabrice L
Fabrice La year ago

You could replace

if(s.Length==1) // One char string for sure would not be balanced return false;

by

if(s.Length%2==1) return false;

Any odd length would be unbalanced.

Naman Jindal
Naman Jindala year ago

But what about the input string "(((" or something like that? your algo is returning true in this case

On this page