current position:Home>Leetcode bracket problem

Leetcode bracket problem

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

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

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

copyright notice
author[Linchong Fengxue mountain temple],Please bring the original link to reprint, thank you.
https://en.chowdera.com/2022/131/202205102050274317.html

Random recommended