Given a string, check if the parentheses are balanced.
Question Explain
Your task in the question is to check if the parentheses in a string are balanced. Balanced parentheses require every opening parenthesis to be closed in the reverse order of their openings. For example, "(()())" and "()(())" are examples of balanced parentheses, while ")())(()" and "(()" are not.
To solve this, you can use a Stack data structure.
-
Scan the string from left to right.
-
Every time you encounter an opening parenthesis, "push" it onto the stack.
-
When you encounter a closing parenthesis, check the stack:
a. If the stack is empty, the parentheses are not balanced. b. If the stack is not empty, "pop" a parenthesis from the stack.
-
When you have finished scanning the string, the stack should be empty if the parentheses are balanced.
Answer Example 1
For example, if you are given a string s = "(()())", the steps would be:
-
Scan the string:
1. '(' is an opening parenthesis and put it into the stack ['(']. 2. '(' again, add it into the stack ['(', '(']. 3. ')' is a closing parenthesis, remove the last opening parenthesis in the stack ['(']. 4. '(' add it into the stack ['(', '(']. 5. ')' remove the last opening parenthesis in the stack ['(']. 6. ')' remove the last opening parenthesis in the stack [].
As the stack is empty after scanning the whole string, it means the parentheses are balanced in this string.
Answer Example 2
For another example, if you are given a string s = "(()", the steps would be:
-
Scan the string:
1. '(' add it into the stack ['(']. 2. '(' add it into the stack ['(', '(']. 3. ')' remove the last opening parenthesis in the stack ['('].
The stack is not empty in the end, so the parentheses are not balanced in this string.
More Questions
- Construct a binary tree given its preorder and inorder traversals.
- Tell me about a system design problem you solved with machine learning.
- Tell me about what your ideal team looks like. Which mix of skills and experience levels would you want? What was your best performing team? Why? What was your worst performing team? Why?
- Estimate the number of Instagram posts per day.
- What are the top 3 apps that you would consider most effective? Why?