Teaching Kids Programming – Check a Valid Parenthese String


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) —

GD Star Rating
loading...
274 words
Last Post: Teaching Kids Programming - List in Python
Next Post: Robinhood Stock Market Return of Investment Calculation Algorithm

The Permanent URL is: Teaching Kids Programming – Check a Valid Parenthese String

Leave a Reply