SWE Prep

Share this post

Valid Parentheses I

sweprep.substack.com

Valid Parentheses I

Sameer Khoja
Jan 7, 2021
Share this post

Valid Parentheses I

sweprep.substack.com

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.

See Approach

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.

Share this post

Valid Parentheses I

sweprep.substack.com
TopNew

No posts

Ready for more?

© 2023 Sameer Khoja
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing