Back to Main
Learn DSA
Depth-First Search
Greedy Algorithms
Get Premium
Stack
Valid Parentheses
easy
DESCRIPTION (credit 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:
Output:
Example 2:
Inputs:
Output:
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 popped 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
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
1x
Login to track your progress
Your account is free and you can post anonymously if you choose.