Question
Python algorithm question Stack question Please find the minimum number of parentheses that should be added to make the input string valid for example, if
- Python algorithm question
- Stack question
- Please find the minimum number of parentheses that should be added to make the input string valid
- for example,
- if s = "()", then the solution should return 0, since no parenthesis needs to be added to make s valid
- if s = "(", then the solution should return 1, since one parenthesis (a right one) needs to be added to make s valid (s = "()")
- if s = ")(", then the solution should return 2, since two parentheses (a left and a right) need to be added to make s valid (s = "()()")
- the parentheses are valid if they are always in pairs and in the correct order
- assume the string only includes '(' and ')'
- Please find the solution with the complexity below,
- Complexity:
- O(n) time
- O(1) space
======================================================================
# implementation here
def exr_1(s): """ Find the minimum number of parentheses that should be added to make the input string valid The parentheses are valid if they are always in pairs and in the correct order You may assume the string only includes '(' and ')' Parameters ---------- s: a string Returns ---------- the minimum number of parentheses that should be added: an integer """
===================================================================
# The output is given,
# Test s_1 = "()" s_2 = "(" s_3 = ")" s_4 = ")(" s_5 = "()()" s_6 = "))(("
print(exr_1(s_1)) print(exr_1(s_2)) print(exr_1(s_3)) print(exr_1(s_4)) print(exr_1(s_5)) print(exr_1(s_6))
0 1 1 2 0 4
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started