Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
class Solution(object):
def isValid(self, s):
stack = [] # create an empty stack to store opening brackets
for c in s: # loop through each character in the string
if c in '([{': # if the character is an opening bracket
stack.append(c) # push it onto the stack
else: # if the character is a closing bracket
if not stack or \
(c == ')' and stack[-1] != '(') or \
(c == '}' and stack[-1] != '{') or \
(c == ']' and stack[-1] != '['):
return False # the string is not valid, so return false
stack.pop() # otherwise, pop the opening bracket from the stack
return not stack # if the stack is empty, all opening brackets have been matched with their corresponding closing brackets,
# so the string is valid, otherwise, there are unmatched opening brackets, so return falseRelated Problems
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.
We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c