Search
⌘K
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 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 parantheses) 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.
Solution
Try these examples:
Visualization
Python
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.