Leetcode - Parentheses

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。

Powered by Hexo and Hexo-theme-hiker

Copyright © 2020 - 2021 DSMI Lab's website All Rights Reserved.

UV : | PV :