В этом посте я расскажу о решении проблемы с leetcode - Допустимые круглые скобки.

Проблема:

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

Строка ввода допустима, если:

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

Пример 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 состоит только из скобок '()[]{}'.

Решение:

Как упоминалось в формулировке задачи, круглые скобки, фигурные скобки и скобки (в тексте ниже я буду называть их скобками) должны быть закрыты одним и тем же типом. т.е. '(' необходимо закрыть до')'. Кажется, это пара персонажей, которые работают вместе. Давайте воспользуемся этой концепцией для построения алгоритма решения этой проблемы.

  1. Создайте карту с именем charMap, на которой будут храниться начальный и соответствующий закрывающий символы.
  2. Наилучшей подходящей структурой данных для этого варианта использования является Stack, поскольку она имеет характер Last-In-First-Out (LIFO), т.е. последний вставленный элемент будет извлечен первым. Итак, давайте создадим переменную stack типа Character.
  3. Для каждого символа во входной строке выполните шаги с №4 по №6.
  4. Если charMap содержит ключ с символом, это означает, что это одна из открывающих скобок, и, следовательно, мы помещаем ее в stack.
  5. В противном случае это одна из закрывающих скобок. Теперь (a) получить верхний элемент из stack с помощью pop()method (b) получить значение для этого элемента из charMap (c) сравнить его с текущим символом в итерации. Если они не совпадают, это означает, что они не соответствуют скобкам, и поэтому мы возвращаем false.
  6. Есть еще один угловой случай, когда закрывающая скобка является последним символом в строке после того, как все совпадающие скобки или закрывающая скобка является единственным символом во входной строке. В этом случае нам нужно добавить еще одно условие or в блок if на шаге 5, чтобы проверить, пуст ли стек.
  7. В конце концов, если стек пуст, все скобки совпадают и, следовательно, мы возвращаем истину. В противном случае верните 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