Teaching Kids Programming: Videos on Data Structures and Algorithms
Yesterday, we talked about the algorithm to check if a given string is a valid parenthese or not. Today, let’s make it a bit interesting. The task is to compute the number of the brackets required in order to make the given string a valid parenthese.
When we determine the string is invalid parenthese, we need to increment the counter instead of exit immediately. At the end, we need to add the number of still opening brackets i.e. balance to the final answer.
At any time, the balance falls below zero, we need to add a matching opening parenthese. We move on (reset the balance counter, as we have repaired it to this point).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def repairParenthese(s): bal = 0 ans = 0 for i in s: if i == "(": bal += 1 elif i == ")": bal -= 1 if bal < 0: # invalid, thus need to insert ans += 1 bal = 0 # invalid if bal is not zero, # need to fully close 'bal' parentheses return bal + ans |
def repairParenthese(s):
bal = 0
ans = 0
for i in s:
if i == "(":
bal += 1
elif i == ")":
bal -= 1
if bal < 0:
# invalid, thus need to insert
ans += 1
bal = 0
# invalid if bal is not zero,
# need to fully close 'bal' parentheses
return bal + ans–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
287 wordsloading...
Last Post: Robinhood Stock Market Return of Investment Calculation Algorithm
Next Post: Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem
