Question: Given a string containing just the characters ’(’, ’)’, ’’, ’’, ’[’ and ’]’, determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]" are all valid but "(]" and "([)]" are not.
Solution
This solution can be found using a Stack. We push values into the stack if they match a starting character “(“, “[“, and if we encounter a ending character we check if
The stack is not empty
If
stack.peek()== the corresponding starting character of this ending character
If both of these cases are true, we pop the character from the stack and continue. If either of these cases are false, know the parentheses is not valid and can return false since the stack should not be empty if we are encountering an ending character (has to be a corresponding start for every end), and whatever stack.peek() is now should not be a different character other than the corresponding starting character.
We’re done!
Interested in breaking into Computer Science? Eager to expand your knowledge base and learn new things? Enjoy problem solving? If so, this newsletter is for you. Subscribe to get fully explained interview prompts commonly given in engineering interviews, from Arrays to Dynamic Programming. Questions come out weekly and are also categorized by subject and difficulty.
Subscribe to get full access to the newsletter. Never miss an update.