Valid Parentheses
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.
EXAMPLES
Example 1:
Inputs:
s = "(){({})}"
Output:
True
Example 2:
Inputs:
s = "(){({}})"
Output:
False
Run your code to see results here
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
Loading comments...