Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a Parenthese (aka brackets) string that only contains “(” or “)” return if it is a valid Parenthese i.e. every starting “(” should match a closing “)” and you should not close “)” without a matched “(“. Also, every “(” should be closed “)”.
For example, “” empty string should be valid. And “()”, “()()”, “()(())” are valid, but “)(“, “())”, “())(” are not valid Parentheses.
Valid Parenthese String Algorithm
We can use a variable/counter to keep tracking of the current opening brackets. That is, when we have opening “(“, we increment the counter, and when we meet “)”, we decrement it. The counter must not fall below zero. And at the end, we should have a counter that is valued zero.
1 2 3 4 5 6 7 8 9 10 | def validParentheses(s): b = 0 for i in s: if i == '(': b += 1 elif i == ')': b -= 1 if b < 0: return False return b == 0 |
def validParentheses(s): b = 0 for i in s: if i == '(': b += 1 elif i == ')': b -= 1 if b < 0: return False return b == 0
As we are going through the N characters in the string, the time complexity is O(N) and the space complexity is O(1) constant.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - List in Python
Next Post: Robinhood Stock Market Return of Investment Calculation Algorithm