В этом посте я расскажу о решении проблемы с leetcode - Допустимые круглые скобки.
Проблема:
Учитывая строку s
, содержащую только символы '('
, ')'
, '{'
, '}'
, '['
и ']'
, определите, является ли входная строка допустимой.
Строка ввода допустима, если:
- Открытые скобки должны закрываться скобками того же типа.
- Открытые скобки должны быть закрыты в правильном порядке.
Пример 1:
Input: s = "()" Output: true
Пример 2:
Input: s = "()[]{}" Output: true
Пример 3:
Input: s = "(]" Output: false
Пример 4:
Input: s = "([)]" Output: false
Пример 5:
Input: s = "{[]}" Output: true
Ограничения:
1 <= s.length <= 104
s
состоит только из скобок'()[]{}'
.
Решение:
Как упоминалось в формулировке задачи, круглые скобки, фигурные скобки и скобки (в тексте ниже я буду называть их скобками) должны быть закрыты одним и тем же типом. т.е. '('
необходимо закрыть до')'
. Кажется, это пара персонажей, которые работают вместе. Давайте воспользуемся этой концепцией для построения алгоритма решения этой проблемы.
- Создайте карту с именем
charMap
, на которой будут храниться начальный и соответствующий закрывающий символы. - Наилучшей подходящей структурой данных для этого варианта использования является
Stack
, поскольку она имеет характер Last-In-First-Out (LIFO), т.е. последний вставленный элемент будет извлечен первым. Итак, давайте создадим переменнуюstack
типа Character. - Для каждого символа во входной строке выполните шаги с №4 по №6.
- Если
charMap
содержит ключ с символом, это означает, что это одна из открывающих скобок, и, следовательно, мы помещаем ее вstack
. - В противном случае это одна из закрывающих скобок. Теперь (a) получить верхний элемент из
stack
с помощьюpop()
method (b) получить значение для этого элемента изcharMap
(c) сравнить его с текущим символом в итерации. Если они не совпадают, это означает, что они не соответствуют скобкам, и поэтому мы возвращаем false. - Есть еще один угловой случай, когда закрывающая скобка является последним символом в строке после того, как все совпадающие скобки или закрывающая скобка является единственным символом во входной строке. В этом случае нам нужно добавить еще одно условие
or
в блок if на шаге 5, чтобы проверить, пуст ли стек. - В конце концов, если стек пуст, все скобки совпадают и, следовательно, мы возвращаем истину. В противном случае верните false.
Вот как выглядит код -
class Solution { private static final Map<Character, Character> charMap = new HashMap<>(); static { charMap.put('(', ')'); charMap.put('[', ']'); charMap.put('{', '}'); } public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (char ch : s.toCharArray()) { if (charMap.containsKey(ch)) { stack.push(ch); } else { if (stack.empty() || ch != charMap.get(stack.pop())) { return false; } } } return stack.empty(); } }
Надеюсь это поможет! Удачного кодирования! 🙂
Если вы думаете, что решение можно улучшить или что-то упускает, не стесняйтесь комментировать. Всегда есть возможности для улучшения.
Найдите решения для проблем с leetcode здесь - https://github.com/rishikeshdhokare/leetcode-problems