## current position：Home>Leetcode bracket problem

# Leetcode bracket problem

2022-05-15 07:49:17【Linchong Fengxue mountain temple】

# 678. Valid bracket string

## greedy

Only left and right parentheses , Essentially also based on

Number of last left parentheses = Number of right parentheses , And traverse to the current subscript , The number of left parentheses must be greater than or equal to the number of right parentheses

```
class Solution {
public boolean checkValidString(String s) {
int min = 0, max = 0; // Maintain the quantity range of the current left parenthesis ：[min, max]
char[] chars = s.toCharArray();
for(char i : chars) {
if(i == '(') {
min++;
max++;
}else if(i == ')') {
//min > 0 only --
if(min > 0) min--;
if(max-- == 0) return false;
}else {
//min > 0 only --
if(min > 0) min--;
max++;
}
}
return min == 0;
}
}
author ：codeppx
link ：https://leetcode.cn/problems/valid-parenthesis-string/solution/codepi-pi-xia-shuang-zhan-tan-xin-si-lu-bua32/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .
```

# 6059. Check whether there are legal parenthesis string paths

## to flash back ： Overtime

```
class Solution(object):
def hasValidPath(self, grid):
"""
:type grid: List[List[str]]
:rtype: bool
"""
def check(alist):
stack = [alist[0]]
for i in range(1, len(alist)):
if stack and alist[i] == stack[-1]:
stack.append(alist[i])
else:
if stack:
stack.pop()
else:
stack.append(alist[i])
if len(stack) == 0:
return True
return False
directions = [(1,0),(0,1)]
def dfs(start_x,start_y,left,right):
if right > left:
return False
if start_x == len(grid)-1 and start_y == len(grid[0])-1:
print(path)
if check(path):
return True
else:
return False
for direction in directions:
new_x = start_x + direction[0]
new_y = start_y + direction[1]
if new_x >= 0 and new_x <=len(grid)-1 and new_y >=0 and new_y <=len(grid[0])-1:
path.append(grid[new_x][new_y])
if grid[new_x][new_y] == "(":
left += 1
if grid[new_x][new_y] == ")":
right += 1
if dfs(new_x,new_y,left,right):
return True
path.pop()
return False
# A special case
path = []
path.append(grid[0][0])
if grid[0][0] == "(":
return dfs(0,0,1,0)
if grid[0][0] == ")":
return False
```

## to flash back + Bracket judgment

As long as it's not with list Backtracking , It can be used lru_cache Of .

Be sure to go back , Because it is for Adding and subtracting values in a loop

for direction in directions:

new_x = start_x + direction[0]

new_y = start_y + direction[1]

if new_x >= 0 and new_x <= len(grid) - 1 and new_y >= 0 and new_y <= len(grid[0]) - 1:

if grid[new_x][new_y] == "(":

left_count += 1

if grid[new_x][new_y] == ")":

right_count += 1

Without backtracking for The loop will be right left_count and right_count To cover .

```
class Solution:
def hasValidPath(self, grid: List[List[str]]) -> bool:
directions = [(1,0),(0,1)]
@lru_cache(None)
def dfs(start_x,start_y,left_count,right_count):
if right_count > left_count:
return False
if start_x == len(grid) - 1 and start_y == len(grid[0]) - 1:
if left_count == right_count:
return True
else:
return False
for direction in directions:
new_x = start_x + direction[0]
new_y = start_y + direction[1]
if new_x >= 0 and new_x <= len(grid) - 1 and new_y >= 0 and new_y <= len(grid[0]) - 1:
if grid[new_x][new_y] == "(":
left_count += 1
if grid[new_x][new_y] == ")":
right_count += 1
if dfs(new_x, new_y, left_count,right_count):
return True
if grid[new_x][new_y] == "(":
left_count -= 1
if grid[new_x][new_y] == ")":
right_count -= 1
return False
if grid[0][0] == ")":
return False
return dfs(0,0,1,0)
```

## Memory deep search + Bracket judgment

Solve three bracket related algorithm problems hand in hand

With only parentheses , You don't have to use a stack . The way to judge is

The number of left parentheses is finally equal to the number of right parentheses , And the number of left parentheses at any position must not be less than the number of right parentheses .

Without backtracking , Can't be in for Change in the loop dfs Parameter values for

```
class Solution:
def hasValidPath(self, grid: List[List[str]]) -> bool:
@lru_cache(None)
def dfs(i, j, c):
if c < 0 or i == m or j == n:# When the quantity is less than 0 Or beyond the boundary is illegal
return False
c = c + 1 if grid[i][j] == "(" else c - 1# Number of updates
return c == 0 if i == m - 1 and j == n - 1 else dfs(i + 1, j, c) or dfs(i, j + 1, c) # If you have reached the lower right corner, return whether it is legal according to the quantity , Otherwise, continue to search deeply
m, n = len(grid), len(grid[0])
return dfs(0, 0, 0)
author ：qin-qi-shu-hua-2
link ：https://leetcode-cn.com/problems/check-if-there-is-a-valid-parentheses-string-path/solution/python-ji-yi-hua-shen-sou-by-qin-qi-shu-5yhnr/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .
```

# 301 Remove invalid parentheses

## Failed all case Solution method

```
# First count the number of left and right parentheses , List the left and right parentheses that need to be deleted , Then enumerate the left and right parentheses that need to be deleted
# Pay attention to the validity of parentheses when backtracking
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
def cal_delete(s):
left_count = 0
right_count = 0
for i in range(len(s)):
if s[i] == "(":
left_count += 1
elif s[i] == ")":
right_count += 1
return left_count, right_count
def isvalid(s):
left = 0
for i in range(len(s)):
if s[i] == "(":
left += 1
elif s[i] == ")":
left -= 1
if left < 0:
return False
return left == 0
def cal_path(path):
cur_res = []
for i in range(len(s)):
if i not in path:
cur_res.append(s[i])
return "".join(cur_res)
# flag by 1 Indicates that the left parenthesis needs to be deleted , by 0 Indicates that the closing bracket needs to be deleted
def dfs(index, need_del_count, flag):
if need_del_count == 0:
cur_res = cal_path(path)
if isvalid(cur_res) and cur_res not in res:
res.append(cur_res)
for i in range(index, len(s)):
if flag == 1:
if s[i] == "(" and need_del_count > 0:
path.append(i)
dfs(i + 1, need_del_count - 1, flag)
path.pop()
else:
dfs(i + 1, need_del_count, flag)
if flag == 0:
if s[i] == ")" and need_del_count > 0:
path.append(i)
dfs(i + 1, need_del_count - 1, flag)
path.pop()
else:
dfs(i + 1, need_del_count, flag)
res = []
path = []
left_count, right_count = cal_delete(s)
if left_count > right_count:
need_del_count = left_count - right_count
flag = 1
else:
need_del_count = right_count - left_count
flag = 0
dfs(0, need_del_count, flag)
if len(res) == 0:
return [""]
return res
```

## to flash back + Bracket judgment

```
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
# Count the number of left parentheses and right parentheses to be deleted ,
# Note that the number of left and right parentheses cannot be counted, and then the two are subtracted , Because, for example ")(" This situation . Be sure to consider the order of precedence
def del_count(s):
left_remove = 0
right_remove = 0
for i in range(len(s)):
if s[i] == "(":
left_remove += 1
elif s[i] == ")":
if left_remove > 0:
left_remove -= 1
else:
right_remove += 1
return left_remove, right_remove
def is_valid(s):
left = 0
for i in range(len(s)):
if s[i] == "(":
left += 1
elif s[i] == ")":
left -= 1
if left < 0:
return False
return left == 0
left_remove, right_remove = del_count(s)
path = []
res = []
def dfs(index, left_remove, right_remove, diff):
if diff < 0:
return
if left_remove == 0 and right_remove == 0 and index == len(s):
cur_res = "".join(path[:])
if is_valid(cur_res) and cur_res not in res:
res.append(cur_res)
return
if index == len(s):
return
if s[index] == "(":
# To the current left parenthesis
path.append(s[index])
dfs(index + 1, left_remove, right_remove, diff + 1)
path.pop()
# Do not use the current left parenthesis
if left_remove > 0:
dfs(index + 1, left_remove - 1, right_remove, diff)
elif s[index] == ")":
# To the current closing bracket
path.append(s[index])
dfs(index + 1, left_remove, right_remove, diff - 1)
path.pop()
# Don't use the current closing bracket
if right_remove > 0:
dfs(index + 1, left_remove, right_remove - 1, diff)
else:
path.append(s[index])
dfs(index + 1, left_remove, right_remove, diff)
path.pop()
dfs(0, left_remove, right_remove, 0)
return res
```

copyright notice

author[Linchong Fengxue mountain temple],Please bring the original link to reprint, thank you.

https://en.chowdera.com/2022/131/202205102050274317.html

## The sidebar is recommended

- Which securities company does qiniu school recommend? Is it safe to open an account
- Hyperstyle: complete face inversion using hypernetwork
- What activities are supported by the metauniverse to access reality at this stage?
- P2P swap OTC trading on qredo
- Google | coca: the contrast caption generator is the basic image text model
- SIGIR 2022 | Huawei reloop: self correcting training recommendation system
- Whether you want "melon seed face" or "national character face", the "face changing" technology of Zhejiang University video can be done with one click!
- Sorting of naacl2022 prompt related papers
- Servlet create project
- "Chinese version" Musk was overturned by the original: "if it's true, I want to see him"

## guess what you like

[network security] web security trends and core defense mechanisms

[intensive reading] object detection series (10) FPN: introducing multi-scale with feature pyramid

007. ISCSI server chap bidirectional authentication configuration

2021-03-09

plot_ Importance multi classification, sorting mismatch, image value not displayed

[intensive reading] object detection series (XI) retinanet: the pinnacle of one stage detector

How to install MFS environment for ECS

[intensive reading] the beginning of object detection series (XII) cornernet: anchor free

Open source sharing -- a record of students passing through time

MOT：A Higher Order Metric for Evaluating Multi-object Tracking

## Random recommended

- How to develop a distributed memory database (1)
- Reverse engineers reverse restore app and code, and localization is like this
- One line command teaches you how to export all the libraries in anaconda
- Bi tools are relatively big. Let's see which one is most suitable for you
- Read the history of database development
- Self cultivation of coder - batterymanager design
- Technology application of swift phantom type phantom in Apple source code learning
- Swiftui advanced skills: what is the use of the technology of swift phantom type phantom
- Swiftui advanced animation Encyclopedia of complex deformation animation is based on accelerate and vector arithmetic (tutorial includes source code)
- What problems remain unsolved in swiftui in 2022
- I'll set the route for fluent
- Flutter drawing process analysis and code practice
- Emoji language commonly used icon collection (interesting Emoji)
- 5.14 comprehensive case 2.0 - automatic induction door
- How to deploy redis service on k8s top?
- Importance of data warehouse specification
- Idea automatically generates serialization ID
- Why is it recommended not to use select * in MySQL?
- Let's talk about why redis needs to store two data structures for the same data type?
- Domain lateral move RDP delivery
- gDvuGqjmDS
- [learn slam orb_slam2 or slam3 from scratch] summary of all blog articles
- 20000 + star ultra lightweight OCR system pp-ocrv3 effect increased by 5% - 11%!
- A configurable canvas clock - Super multi style
- The pp-ocrv3 effect of 20000 + star ultra lightweight OCR system is further improved by 5% - 11%
- MySQL's golden rule: "don't use select *"
- True interview question: why does redis store a data type twice?
- High threshold for large factories? Five exclusive PDFs inside Alibaba will take you forward and win the offer
- Is it really hard to find a job? How on earth can I find a job with high salary without worrying about being laid off
- How to design knowledge center? (code attached)
- OWASP top 10 vulnerability analysis
- Are you still writing comment templates manually? Idea can generate annotation templates of classes and methods with one click. Click in if you don't know
- Numpy core syntax and code sorting summary!
- Can you believe that the swoole timer can realize millisecond task scheduling?
- Detailed explanation of art template engine
- Telephone subsystem of openharmony source code analysis -- call flow
- Yixin Huachen: how to do a good job in digital transformation in the power industry?
- One stop collaboration is really delicious - apipost
- Notes on modern algebra and series of questions: Chapter 1 (introduction of algebraic system)
- Notes on modern algebra and serialization of question types: Chapter 2 (properties of binary operation)