# Leetcode bracket problem

2022-05-15 07:49:17 # 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

Power button ``````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
source ： Power button （LeetCode）

# 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]
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)-1:
print(path)
if check(path):
return True
else:
return False
for direction in directions:
new_x = start_x + direction
new_y = start_y + direction
if new_x >= 0 and new_x <=len(grid)-1 and new_y >=0 and new_y <=len(grid)-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)
if grid == "(":
return dfs(0,0,1,0)
if grid == ")":
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
new_y = start_y + direction
if new_x >= 0 and new_x <= len(grid) - 1 and new_y >= 0 and new_y <= len(grid) - 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) - 1:
if left_count == right_count:
return True
else:
return False
for direction in directions:
new_x = start_x + direction
new_y = start_y + direction
if new_x >= 0 and new_x <= len(grid) - 1 and new_y >= 0 and new_y <= len(grid) - 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 == ")":
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)
return dfs(0, 0, 0)

author ：qin-qi-shu-hua-2
source ： Power button （LeetCode）

# 301 Remove invalid parentheses Power button

## 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
``````