Это часть моей серии, где я участвую в MeMo от LeetCode. Если у вас есть лучшие решения или идеи, пожалуйста, оставьте комментарий!
Проблемы
Допустимые скобки
Мы должны проверить данную строку действительную скобки. Данная строка недействительна при отсутствии правой или левой скобки или порядок скобок неверно.
Например, “([])” -> ОК “() [] {}” -> ОК “[] (()” -> ng “([)]” -> ng “]” -> ng
Подход
Стек и карта полезны для этого вопроса. Мы посмотрим данную строку в порядке спереди. Когда CHAR – левая сторона скобки, добавьте его в стек, и когда Char является правой стороны скобки, верхнее значение POP Stack и проверьте, действителен или нет с помощью карты. Поэтому мы должны установить карту, как показано ниже,
скобки_Мап = [“)”: “(“, “}”: “{“, “]”: “[“]
Наконец, если стек пуст, строка действительна.
Решение
class Solution:
def isValid(self, s: str) -> bool:
stack = []
parentheses_map = {")":"(", "}":"{", "]":"["}
for i in s:
if i in parentheses_map:
stack_top = stack.pop() if stack else ' '
if parentheses_map[i] != stack_top:
return False
else:
stack.append(i)
return not stack
Примечание: В вышеупомянутом коде решения, когда стек пуст, мы должны назначить фиктивное значение, потому что если запись как ниже,
if stack:
stack_top = stack.pop()
случай S Будем быть правдой, и это неверный ответ.
Спасибо за прочтение этой статьи! Я всегда приветствую ваши отзывы, вопрос и идею.
Оригинал: “https://dev.to/shoryu/valid-parentheses-4d32”