Правильные круглые скобки

Проблема Leetcode: Действительные родительские скобки

Задача:

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

Входная строка является допустимой, если:

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

Шаблон: Стек

Подход:

1. Используйте хэш-карту для хранения парных скобок: ключ = закрытая скобка и значение = открытая скобка.
2. Если хэш-карта не содержит текущего символа, то это открытая скобка. Используйте стек для хранения открытых скобок.
3. Проверьте, не пуст ли стек, это предотвращает добавление закрытых скобок первыми, в этом случае он не действителен.
4. Проверьте вершину стека, открыв его, и если верхний символ не совпадает с закрывающей скобкой в hashmap, то верните false.
5. Если стек пуст, то верните true, так как это правильная скобка.
6. Если стек не пуст, то верните false.

Нотация Big-O:

Временная сложность: O(n)
Мы выполняем итерацию n раз для каждого символа в строке.

Сложность пространства: O(n)
Для хранения данных мы используем структуру хэш-карт.

Код:

class Solution {

    public boolean isValid(String s) {
        // use stack to store opening brackets
        Stack <Character> stack = new Stack<>();

        // use a hashmap to store pairs 
        Map <Character, Character> hashMap = new HashMap<>();
        hashMap.put(')','(');
        hashMap.put('}','{');
        hashMap.put(']','[');

        // iterate through s
        // add open brackets to the stack
        // if stack is empty or top char is not a match to c 
        // return false 

        for(char c : s.toCharArray()){
            if(!hashMap.containsKey(c)){
                stack.push(c);
            } else if(stack.isEmpty() || stack.pop() != hashMap.get(c)){
                   return false;
                }
            }
        return stack.isEmpty();        
    }
}