Determining the validity of parentheses can be efficiently handled using a "stack" data structure.
We traverse the given string s. When we encounter a left parenthesis, we expect to find a corresponding right parenthesis of the same type later in the traversal. As the most recently encountered left parenthesis should be closed first, we can push it onto the top of the stack.
When we encounter a right parenthesis, we need to close off a left parenthesis of the same type. At this point, we can pop the top left parenthesis from the stack and check if they are of the same type. If they are not the same type, or if there is no left parenthesis in the stack, then the string s is invalid, and we should return False. To quickly determine the type of parentheses, we can use a hash table, where the keys are right parentheses and the values are the corresponding left parentheses.
After the traversal, if the stack is empty, it means we have closed all the left parentheses in the string s, and we should return True. Otherwise, we return False.
It's important to note that the length of a valid string must be even. Therefore, if the string's length is odd, we can return False directly, avoiding the need for further traversal and checks.
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False
pairs = {
")": "(",
"]": "[",
"}": "{",
}
stack = list()
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack