Условие задачи: дана строка, содержащая только символы '(', ')', '{', '}', '[' и ']', определить, является ли последовательность скобок правильной.
Последовательность скобок считается правильной, если:
- каждая открывающая скобка имеет соответствующую закрывающую скобку,
- последовательность скобок может быть пустой,
- скобки должны закрываться в правильном порядке.
Примеры: Вход: "()", Выход: true Вход: "()[]{}", Выход: true Вход: "(]", Выход: false Вход: "([)]", Выход: false Вход: "{[]}", Выход: true
Решение:
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()) {
if(c=='(' || c=='{' || c=='[') { // если символ - открывающая скобка, помещаем его в стек stack.push(c);
} else if(!stack.isEmpty() && ((c==')' && stack.peek()=='(') || (c=='}' && stack.peek()=='{') || (c==']' && stack.peek()=='['))) { // если символ - закрывающая скобка и она соответствует верхней скобке в стеке, удаляем верхнюю скобку из стека stack.pop();
} else { // иначе последовательность неправильная return false;
}
}
return stack.isEmpty(); // если стек пустой, то последовательность правильная }
}
Идея алгоритма заключается в использовании стека для хранения открывающих скобок. При каждом обнаружении символа скобки мы определяем, является ли он открывающей скобкой или закрывающей. Если это открывающая скобка, мы помещаем его в стек. Если это закрывающая скобка, мы удаляем соответствующую открывающую скобку из стека. Если стек оказывается пустым в конце строки, это означает, что последовательность была правильной.
1606 вопрос-ответ по Java: https://github.com/DEBAGanov/interview_questions
Tелеграмм канал: https://t.me/DEBAGanov
Мое резюме: https://github.com/DEBAGanov