20. Valid Parentheses (easy)
Given a string 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.
Note that an empty string is also considered valid.
example 1
Input: “()”
Output: true
example 2
Input: “()[]{}”
Output: true
example 3
Input: “(]”
Output: false
example 4
Input: “([)]”
Output: false
example 5
Input: “{[]}”
Output: true
Solution Stack!!!!!!
22. Generate Parentheses (medium)
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
Solution Backtracking!!!!!!
x : 紀錄’(‘的個數
l : 紀錄這x個’(‘中,還有幾個沒有match到 ‘)’
32. Longest Valid Parentheses (Hard)
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
example 1
Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”
example 2
Input: “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”
Solution 還是stack!!!!!!
stack_list : 紀錄’(‘的index。