Решение задачи #20. Python LeetCode, Valid Parentheses

Задача на проверку корректности скобочных последовательностей в Python. Это классическая алгоритмическая задача на использование стека, часто встречающаяся на собеседованиях в IT-компаниях.

Вариант решения задачи на Python с LeetCode

Категория: Алгоритмы.
Название задачи: Valid Parentheses.
Сложность: Легкая.
Статус решения: "Решено".

Условие задачи:
Дана строка s, состоящая только из символов '(', ')', '{', '}', '[' и ']'. Определите, является ли входная строка допустимой.

Входная строка считается допустимой, если:

Каждая открывающая скобка должна быть закрыта скобкой того же типа.

Например, () — допустимо, (] — нет.

Скобки должны закрываться в правильном порядке.

Например, ({}) — допустимо, ({)} — нет.

Каждая закрывающая скобка должна иметь соответствующую открывающую скобку того же типа.

Например, ()[]{} — допустимо, (] — нет.

Решение:

Python

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        # Создаем словарь для соответствия открывающих и закрывающих скобок
        brackets_map = {')': '(', '}': '{', ']': '['}
        # Создаем стек для хранения открывающих скобок
        stack = []
        
        # Проходим по каждому символу в строке
        for char in s:
            # Если символ - закрывающая скобка
            if char in brackets_map:
                # Извлекаем последнюю открывающую скобку из стека
                # Если стек пуст, используем заглушку
                top_element = stack.pop() if stack else '#'
                
                # Проверяем соответствие скобок
                if brackets_map[char] != top_element:
                    return False
            else:
                # Если символ - открывающая скобка, добавляем в стек
                stack.append(char)
        
        # Строка валидна, если стек пуст в конце
        return not stack

Мы рассмотрели пример решения, который был принят и засчитан платформой LeetCode как правильный, но вы можете найти свой способ решения задачи, возможно лучше.

Источник решения: hdhai.com