Написано: 26.02.2023

20. Наибольший общий префикс (Valid Parentheses)

easy

Задание.

Дана строка s, содержащая только символы (, ), {, }, [ и ]

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

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

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

Пример 1.

Входные данные: s = “()”

Результат: true

Пример 2.

Входные данные: s = “()[]{}”

Результат: true

Пример 3.

Входные данные: s = “(]”

Результат: false

Решение.

class Solution {
public:
    bool isValid(string s) {
        stack<char> st ;
        char ch, top;
        for (int i = 0 ;  i< s.length() ; i++) {
            if ((ch = s[i]) == '(' || ch == '{' || ch == '[') {
                st.push(ch) ;
            } else if (ch == ')' || ch == '}' || ch == ']') {
                if (st.empty()) {
                    return false ;
                }
                top = st.top() ;
                if((ch == ')' && top != '(')
                    || (ch == '}' && top != '{')
                    || (ch == ']' && top != '[')
                )  {
                    return false ;
                }
                st.pop() ;
            }
        }

        return st.empty();
    }
};