Условия задачи
Учитывая строку s, содержащую только символы ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ и ‘]’, определите, является ли входная строка допустимой.
Входная строка допустима, если:
Открытые скобки должны быть закрыты скобками того же типа.
Открытые скобки должны быть закрыты в правильном порядке.
Каждой закрывающей скобке соответствует открытая скобка того же типа.
Примеры
Example 1:
Input: s = «()»
Output: true
Example 2:
Input: s = «()[]{}»
Output: true
Example 3:
Input: s = «(]»
Output: false
Example 4:
Input: s = «([])»
Output: true
Ограничения
Constraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'.
Рассуждение
Первое что приходит в голову это посчитать количество открывающихся и закрывающихся скобок с учетом 3х видов скобок:
- Фигурных {}
- Квадрaтных []
- Круглых ()
public static boolean isValid(String s) throws UnexpectedException {
// Если у нас пустая строка, то принимаем её за валидную
if (s.isEmpty()) return true;
// Число символов в строке должно быть четным, так как у каждой скобки должна быть парная ей закрывающаяся скобка
if (s.length() % 2 == 1) return false;
// a - (, aa - ), b = [, bb - ], c - {, cc - }
int a = 0, aa = 0, b = 0, bb = 0, c = 0, cc = 0;
for (int i = 0; i < s.length(); i++) {
switch (s.charAt(i)) {
case '{':
c++;
break;
case '}':
cc++;
break;
case '[':
b++;
break;
case ']':
bb++;
break;
case '(':
a++;
break;
case ')':
aa++;
break;
default:
// по условию методам валидации на LeetCode эту строчку нуэно заменить на
// return false; // а так же убрать UnexpectedException в сигнатуре метода
throw new UnexpectedException("Invalid character '" + s.charAt(i) + "'");
}
}
// Краткая форма записи проверки что количество открывающихся и закрывающиъся скобок попарно равно с учетом их вида
return a == aa && b == bb && c == cc;
}Это решение не подойдет по причине того, что не учитывает условие из задачи: Открытые скобки должны быть закрыты в правильном порядке.
Что за правильный порядок?
- Каждая открывающая скобка должна иметь соответствующую закрывающую
- Скобки должны быть закрыты в обратном порядке, в котором они были открыты (принцип «стековой» структуры).
Теперь мы понимаем, что:
({[]}) — правильно
([)] — неправильно (нарушен порядок)
А так же в самом определении этого правильного порядка есть подсказка, которая нам помогает понять, что нужно использовать именно стек в качестве структуры данных.
Решение
Практическое применение
Собственная реализация синтаксического анализатора, популярная задача с собеседования
