abc Interview Question
Senior Software Development EngineersCountry: India
Interview Type: In-Person
step 1 : if there is a opening character increment by 1, start with 0, if there is a closing character then decrement that by 1.
step 2: repeat the step no 1 by applying each characters set '()', '{}, or []
step 3: make sure the result should be 0 at the end
step 4 : make sure the result will never be in negative in the process.
My thinking would be starting with and empty string and then going through on the input string and keep them concatenating to my empty string variable. Then, at each iteration you would only care for last two characters of this variable! if they are a match pair eliminate them. So for example:
starting initialization:
s = "" // empty string
1st input character {
s = "{"
since we do not have yet 2 characters at least, we continue
2nd input character [
s = "{["
the last two characters do not match, so we do nothing
3rd character (
s = "{[("
the last two characters of s are "[" and "(" they do not match so we do nothing
4th character )
s = "{[()" the last two characters are a matching pair "()" so we remove them se becomes:
s = "{["
next character, and so on
if at the end we get an empty string the the brackets are valid
You can use stack and do the following steps
- If the current character is an open parenthesis like “{“ or “(“ or “[“ , push it to the stack
- If the current character is an close parenthesis like “}” or “)” or “]”
o check the latest value in the stack if it is the closer of the latest element on the stack, pop the latest value from the stack
o Otherwise, break from the loop and this string will be invalid.
- Finally, check if there is any element on the stack that is meaning this string is invalid, otherwise, it is valid.
See the below java example
- Badawy December 20, 2017