Stack
Valid Parentheses
easy
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given an input string s consisting solely of the characters '(', ')', '{', '}', '[' and ']', determine whether s is a valid string. A string is considered valid if every opening bracket is closed by a matching type of bracket and in the correct order, and every closing bracket has a corresponding opening bracket of the same type.
Example 1:
Inputs:
s = "(){({})}"
Output:
True
Example 2:
Inputs:
s = "(){({}})"
Output:
False
Explanation
The input string can contain nested brackets which must adhere to a Last-In, First-Out ordering (i.e. if our input string is {[, then the closing ] must come before the closing }). For this reason, our solution will use a stack.
The solution iterates through the string. Whenever it encounters an opening bracket, the bracket is pushed onto the stack. When it encounters a closing bracket, we check to see if it is the corresponding closing bracket for the opening bracket at the top of the stack. If it is, we pop from the stack (because we have found a matching pair) and continue iterating. If it isn't, the string is invalid, and we return False.
The string is valid if the stack is empty after iterating through the string.
You might wonder if we can avoid the stack and just count brackets. We can't — counting only tells us that the number of opens and closes match, not that they're properly nested. For example, ([)] has equal opens and closes, but the brackets interleave instead of nesting. Only a stack can catch that, which is why this problem requires O(n) space.
Solution
Visualization
Python
Try these examples:
def isValid(s):stack = []mapping = {")": "(", "}": "{", "]": "["}for char in s:if char in mapping:if not stack or stack[-1] != mapping[char]:return Falsestack.pop()else:stack.append(char)return len(stack) == 0
valid parentheses
0 / 18
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.