Валидные скобки

Источник: https://leetcode.com/problems/valid-parentheses/

Дана строка s, состояшая из символов '(', ')', '{', '}', '[' и']'. Определеить валидна ли последовательность скобок.

Последовательность сокбок валидна:

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

 

Пример 1:

Дано: s = "()"
Результат: true

Пример 2:

Дано: s = "()[]{}"
Результат: true

Пример 3:

Дано: s = "(]"
Результат: false

Пример 4:

Дано: s = "([)]"
Результат: false

Example 5:

Дано: s = "{[]}"
Результат: true

 

Ограничения:

• 1 <= s.length <= 104
• s состоит только из '()[]{}'.

Идея решения

Для проверки валидности выражений в скобках удобно использовать стеки. Каждую открывающую скобку бросаем в стек. Как только встречаем закрывающую скобку, смотрим, что у нас в верхушке стека. Там бует открывающая скобка, но нам нужно сравнить её с типом закрывающей. 

Если тип совпадает, то достаем открывающую скобку из стека и продолжаем просмотр строки. Если тип не совпадает, то последовательность скобок не валидна. Можно возвращать false и завершать сканирование.

По итогам сканирования валидной строки, стек должен получится пустым. Если же открывающих скобок было больше, чем закрывающих, то это тоже не валидная последовательность.

Имплементация

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        Character[] op = {'(', '{', '['};
        Character[] cl = {')', '}', ']'};
        
        List<Character> opening = Arrays.asList(op);
        List<Character> closing = Arrays.asList(cl);
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (opening.contains(c)) {
                stack.push(c);
            } else if (closing.contains(c)) {
                if (stack.isEmpty()) return false;
                Character sc = stack.peek();
                if (sc==null) return false;
                int openingIndex = opening.indexOf(sc);
                if (openingIndex>=0 && cl[openingIndex].equals(c)) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if (!stack.isEmpty()) return false;
        return true;
    }
}