Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

Given a string s of ‘(‘ , ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

  • It is the empty string, contains only lowercase characters, or
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted
Copy the code

Note:

1 <= s.length <= 10^5
s[i] is either'(' , ')', or lowercase English letter.
Copy the code

parsing

Given a string s consisting of ‘(‘, ‘)’ and lowercase English characters. Our task is to remove the minimum number of parentheses ‘(‘ or ‘)’ at any location so that the generated parenthesized string is valid and returned.

Parenthesized strings are valid as follows:

  • Contains only lowercase characters without parentheses
  • It can be written as AB (A concatenated with B), where A and B are valid strings
  • It can be written as (A), where A is A valid string

In fact, this problem is the question out of a mess, the title says curved, but according to several examples we can understand clearly the question, is s in parentheses is not normal, let’s get rid of parentheses is not normal, into a normal string with brackets, this kind of problem is generally naturally thought of stack data structure.

We use the stack to store the invalid parenthesis position, iterating through all the characters in s, and adding it to the stack if the character in the position indexed by I is ‘(‘; If the stack is not empty, a valid parenthesis pair can be formed, and the last element of the stack is popped. If the stack is empty, the current parenthesis is invalid and the i-th index of S is changed to an empty string.

After traversal, only invalid parenthesis indexes are left in the stack. Change the characters of these indexes to null characters in S, and finally return S after transformation.

The time complexity of the whole algorithm is O(N), and the space complexity is O(N).

answer

class Solution(object):
    def minRemoveToMakeValid(self, s):
        result = list(s)
        stack = []
        for i,c in enumerate(result):
            if c == '(':
                stack.append(i)
            elif c == ')':
                if stack:
                    stack.pop()
                else:
                    result[i] = ''
        for i in stack:
            result[i] = ''
        return ''.join(result)

        	      
		
Copy the code

The results

Runtime: 168 ms, faster than 60.45% of Python online submissions for Minimum Remove to Make Valid Parentheses. Memory Usage: The linked submissions in the Python online submission list are listed in the linked list.Copy the code

The original link

Leetcode.com/problems/mi…

Your support is my biggest motivation