Valid Parentheses — это классическая задача на stack.
Смысл задачи: проверить, правильно ли закрываются скобки.
Например:
"()"
"()[]{}"
"{[]}"
валидно.
А вот:
"(]"
"([)]"
"((("
"]"
невалидно.
Когда мы видим открывающую скобку, мы кладём её в стек:
(
[
{
Когда мы видим закрывающую скобку, она должна закрывать последнюю
открытую скобку.
То есть работает принцип:
последняя открытая скобка должна закрыться первой
А это ровно стек:
Last In — First Out
Последним вошёл — первым вышел.
Пример
Строка:
"{[]}"
Идём слева направо.
Видим {:
stack = ["{"]
Видим [:
stack = ["{", "["]
Видим ].
Она должна закрыть последнюю открытую скобку. Последняя — [. Всё хорошо.
stack = ["{"]
Видим }.
Она должна закрыть {. Всё хорошо.
stack = []
В конце стек пустой — значит все скобки закрылись правильно.
Ответ:
true
Невалидный пример
Строка:
"([)]"
Идём:
( -> stack = ["("]
[ -> stack = ["(", "["]
Теперь видим ).
Но последняя открытая скобка — [, а ) закрывает (.
То есть порядок сломан:
ожидали ], но получили )
Ответ:
false
Базовый алгоритм
- Создаём пустой стек.
- Если символ открывающий — кладём в стек.
- Если символ закрывающий:
- стек не должен быть пустым;
- верхняя скобка в стеке должна соответствовать этой закрывающей.
- В конце стек должен быть пустым.
Python
def is_valid(s):
stack = []
pairs = {
")": "(",
"]": "[",
"}": "{",
}
for ch in s:
if ch in "([{":
stack.append(ch)
else:
if not stack:
return False
top = stack.pop()
if top != pairs[ch]:
return False
return len(stack) == 0
Java
import java.util.*;
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
Map<Character, Character> pairs = Map.of(
')', '(',
']', '[',
'}', '{'
);
for (char ch : s.toCharArray()) {
if (ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
} else {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if (top != pairs.get(ch)) {
return false;
}
}
}
return stack.isEmpty();
}
}
Современнее в Java использовать Deque, а не старый Stack:
import java.util.*;
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(
')', '(',
']', '[',
'}', '{'
);
for (char ch : s.toCharArray()) {
if (ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
} else {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if (top != pairs.get(ch)) {
return false;
}
}
}
return stack.isEmpty();
}
}
Почему тут именно stack
Потому что вложенность скобок работает так:
{ [ ( ) ] }
Сначала открылась {, потом [, потом (.
Но закрываться они должны в обратном порядке:
( закрывается первой
[ закрывается второй
{ закрывается последней
То есть структура такая:
открытие: { [ (
закрытие: ) ] }
Это буквально стек.
Complexity
Время:
O(n)
Потому что мы один раз проходим по строке.
Память:
O(n)
В худшем случае вся строка может состоять из открывающих скобок:
"((((((((("
и тогда все они окажутся в стеке.
Главное различение
valid parentheses — это задача не про подсчёт количества скобок.
То есть нельзя просто проверить, что количество ( равно количеству ).
Например:
")("
Количество одинаковое, но строка невалидна.
Почему? Потому что закрывающая скобка появилась раньше открывающей.
Поэтому нужна не frequency map, а именно stack, потому что важен порядок
закрытия.
