PrepBro
← Назад к вопросам

Как решить задачу Valid Parentheses с LeetCode?

1.0 Junior🔥 151 комментариев
#Коллекции и структуры данных

Комментарии (1)

🐱
deepseek-v3.2PrepBro AI5 апр. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Алгоритмическое решение задачи Valid Parentheses

Задача (LeetCode #20) проверяет корректность скобочной последовательности. Необходимо определить, правильно ли расставлены скобки трёх типов: круглые (), квадратные [] и фигурные {}.

Ключевая идея решения

Основной подход использует стек (Stack) для отслеживания открывающих скобок. Алгоритм последовательно обрабатывает каждый символ строки и проверяет соответствие скобок по принципу LIFO (Last-In-First-Out).

Детальный алгоритм

  1. Инициализация стека для хранения открывающих скобок
  2. Обход строки посимвольно:
    • При встрече открывающей скобки (, [, { - помещаем её в стек
    • При встрече закрывающей скобки ), ], }:
     - Если стек пуст - последовательность некорректна
     - Извлекаем последнюю открывающую скобку из стека
     - Проверяем соответствие типов скобок
  1. Финальная проверка - стек должен быть пустым

Реализация на Kotlin

class Solution {
    fun isValid(s: String): Boolean {
        val stack = ArrayDeque<Char>()
        val pairs = mapOf(
            ')' to '(',
            ']' to '[',
            '}' to '{'
        )
        
        for (char in s) {
            when (char) {
                '(', '[', '{' -> stack.addLast(char)
                ')', ']', '}' -> {
                    if (stack.isEmpty()) return false
                    val lastOpen = stack.removeLast()
                    if (lastOpen != pairs[char]) return false
                }
            }
        }
        
        return stack.isEmpty()
    }
}

Реализация на Java

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> pairs = Map.of(
            ')', '(',
            ']', '[',
            '}', '{'
        );
        
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char lastOpen = stack.pop();
                if (lastOpen != pairs.get(c)) return false;
            }
        }
        
        return stack.isEmpty();
    }
}

Анализ сложности

  • Временная сложность: O(n), где n - длина строки. Каждая операция со стеком выполняется за O(1)
  • Пространственная сложность: O(n) в худшем случае, когда все скобки открывающие

Краевые случаи и тестирование

Важно проверять:

  1. Пустую строку - должна считаться валидной
  2. Строку с нечётной длиной - автоматически невалидна
  3. Вложенные скобки разного типа
  4. Неправильную последовательность закрывающих скобок
  5. Несбалансированное количество открывающих и закрывающих скобок

Примеры работы алгоритма

Валидные последовательности:

  • "()[]{}" → true
  • "{[]}" → true
  • "([{}])" → true

Невалидные последовательности:

  • "(]" → false
  • "([)]" → false
  • "(((" → false

Практическое применение

Это классическая задача на стек, часто встречающаяся в:

  • Проверке синтаксиса в компиляторах
  • Анализе JSON/XML структур
  • Реализации калькуляторов и парсеров выражений
  • Проверке корректности HTML/JSX разметки

Решение демонстрирует понимание базовых структур данных и умение применять их для обработки последовательностей с учётом вложенности и порядка элементов.

Как решить задачу Valid Parentheses с LeetCode? | PrepBro