Teaching Kids Programming: Videos on Data Structures and Algorithms
We talk about the algorithm to check if a string is a valid Parenthese. How about if the string can also contain curly braces {}, or square brackets []? In this case, we use a stack to push all the opening brackets/curly brakces/square brackets. And when we meet a closing one, we need to check if it matches the opening one.
Be careful also not to access an element form an empty stack – which we need to invalidate it immediately. At last, we also need to check if the stack is empty, as a valid Parenthese string should not have un-closed parentheses.
1 2 3 4 5 6 7 8 9 10 | def validParenthese(s): st = [] for i in s: if i in ["(", "[", "{"]: st.append(i) elif i in [")", "]", "}"]: if (len(st) == 0) or (not st[-1] + i in ["()", "[]", "{}"]): return False st.pop() return len(st) == 0 |
def validParenthese(s):
st = []
for i in s:
if i in ["(", "[", "{"]:
st.append(i)
elif i in [")", "]", "}"]:
if (len(st) == 0) or (not st[-1] + i in ["()", "[]", "{}"]):
return False
st.pop()
return len(st) == 0–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
266 wordsloading...
Last Post: Simple Vigenère Cipher in C++
Next Post: Convert Base 3 String To Decimal Integer