Simulation volume leetcode [general] 1249 Remove invalid parentheses

1249. Remove invalid brackets

Here you are ‘(’、‘)’ And a string of lowercase letters s.

You need to remove the minimum number of entries from the string ‘(’ perhaps ‘)’ （ You can remove brackets anywhere ), Make the rest 「 Bracket string 」 It works .

Please return any legal string .

It works 「 Bracket string 」 It should conform to the following   Any one of them   requirement ：

Empty strings or strings containing only lowercase letters
Can be written  AB（A  Connect  B） String , among  A  and  B  It's all effective 「 Bracket string 」
Can be written  (A)  String , among  A  Is an effective 「 Bracket string 」

Example 1：

Input ：s = “lee(to)de)”
Output ：“lee(to)de”
explain ：“lee(t(co)de)” , “lee(tode)” It's also a possible answer .
Example 2：

Input ：s = “a)bd”
Output ：“abd”
Example 3：

Input ：s = “))((”
Output ：“”
explain ： Empty strings are also valid
Example 4：

Input ：s = “(a(bd)”
Output ：“a(bd)”

Tips ：

1 <= s.length <= 10^5
s[i]  May be  ‘(’、‘)’  Or English lowercase letters

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/minimum-remove-to-make-valid-parentheses
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

from leetcode_python.utils import *


class Solution:
    def __init__(self):
        pass

    def minRemoveToMakeValid(self, s: str) -> str:
        left,right = 0,s.count(')')
        res = ''
        for char in s:
            print(char,left,right)
            if char=='(':
                if right>0:
                    res += char
                    left+=1
                    right-=1
            elif char==')':
                if left>0:
                    res += char
                    left-=1
                else:
                    right-=1
            else:
                res +=char
        return res


def test(data_test):
    s = Solution()
    data = data_test  # normal
    # data = [list2node(data_test[0])] # list turn node
    return s.minRemoveToMakeValid(*data)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        ["lee(t(c)o)de)"],
        ["))(("],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions _ Paper blog -CSDN Blog

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！