Решаем задачу с JS собеседования — Правильная последовательность скобок | LeetCode задачи

Привет, друзья!
Сегодня решаем с вами задачу про правильную последовательность скобочек. Это очень известная и очень популярная задача на IT собеседованиях. Причем не только на фронтенд собеседованиях! Прислал нам эту задачу наш подписчик ivan rusin, которому она попалась на бэкенд собеседовании.

На Литкоде эта задача easy уровня сложности. На мой взгляд, не такая уж она и easy — не каждый новичок сходу сам осилит.

По условиям: на вход нам приходит строка, содержащая только символы скобок. Следующие символы скобочек: ( ) { } [ ]. Необходимо написать функцию, которая проверит такую строку и вернет в результате true или false — в зависимости от того, является ли данная последовательность скобок валидной или нет.

Вот несколько примеров, чтоб разобраться, что такое валидная, а что такое невалидная последовательность скобок:
"()" // true
"()[]{}" // true
"(]" // false
"([)]" // false
"{[]}" // true

Длина нашей строки может быть от 1 до 10 000 символов. По условию это все.

👍 Присылайте ваше решение в комменатриях! С интересом посмотрю!
👍 Друзья, поддержите наш канал — поставьте этому видео лайк и поделитесь им с друзьями!

Таймкоды:
00:00 Интро
00:41 Условие задачи
02:37 Алгоритм решения в общем виде
04:18 Что такое stack
05:11 Алгоритм решения через stack
07:28 Пишем код
13:22 Проверяем решение
14:36 Сложность алгоритма
14:55 Присылайте ваши решения

---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
---

Присоединяйтесь к нам в соцсетях:

Music:
Blue Wednesday "From a friend",
Blue Wednesday & Dillan Witherow - Long Walk Short Dock.

---
#ityoutubersru​ #фронтенд #алгоритмы #leetcode

[SiniyPetr]

так просто, чтобы было, тоже свое решение оставлю)

function isValidString(str){
let tempStr = str;
let spliters = ['()', '[]', '{}'];
for (let i = 0 ; i < spliters.length ; i++){
if (!tempStr.length) return true;
tempStr =
}
if (str.length === tempStr.length) {
return false;
} else {
return isValidString(tempStr);
}
}


п.с.: спасибо за качественный контент, приятно и смотреть и разбираться вместе над frontend задачами

[Zavyalovvvvv]

да, про стэк было бы полезно послушать... Заранее спасибо!

[romanryaboshtan]

У человека удивительный талант учить, понятно показывать, я такого ещё не видел

[СергейЕрмаков-дл]

Данную задачу уже во второй раз встречаю за свою еще даже не начавшуюся карьеру. Видимо любят ее задавать

[ІльченкоАртем]

Варіант автора відео найвигідніший, найпростіший, найкоротший, на те він і наш вчитель з великим досвідом)

[МаркЮрьев-лс]

Уже пятый день бьюсь над задачей, прохожу на Хекслет курс фронтенд разработчика и мы ещё не дошли до мап, предлагают решить задачу через две константы с открывающимися и закрывающимися скобками через indexOf
Видео очень доступно обьяснило мне ход решения, мне было и так все понятно, но как сравнить скобки без обьекта до сих пор не понял, но обязательно дойду к этому. Спасибо, отлично делаете свое дело, удачи вам!

[alexandervoievodin]

Спасибо за видео! Немного изменил код, кому как больше по вкусу.

function isValid(s) {
const stack = [];
const brackets = {
')': '(',
']': '[',
'}': '{',
};

for (const current of s) {
if (current in brackets) {
if (brackets[current] !== stack.pop()) return false;
} else {
stack.push(current);
}
}

return !stack.length;
}

[alchemynotes]

Блин, я как раз в прошлом месяце искала такой видос :( И нашла только какой-то шестилетней давности :(
Спасибо! Полезно! И монтаж такой клевый, каждый раз приятно удивляюсь :3

[serhiiyeromin]

Раньше решал задачу через два масcива: с символами скобок начала и конца. Принцип тот же, но удобно сопоставлять по номеру вхождения в масив через indexOf. И работает шустрее)
function isBalanced(string) {
const arr = []
const start = ['{', '[', '(']
const end = ['}', ']', ')']
for (let char of string) {
if (start.includes(char))
arr.push(char)
else if (end.includes(char))
if (arr[arr.length-1] === start[end.indexOf(char)])
arr.pop()
else
return false
}
return arr.length === 0
}

[SerzhNesteruk]

Спасибо за видео и интересную задачу! Решение почти полностью совпало с моим (даже нейминг), только цикл в другую сторону. 🙂

const isValidBracketSequence = str => {
const brackets = {
')': '(',
']': '[',
'}': '{',
},
stack = [];
for (let i = str.length - 1; i >= 0; i--) {
let char = str[i];
if (char in brackets) {
stack.push(brackets[char]);
} else if (char !== stack.pop()) {
return false;
}
}
return stack.length === 0;
};

[_alexanderd]

Решил на php за 15 мин где-то через рекурсивный проход. В самом начале сделал проверку на четность кол-ва скобочек, чтобы сразу отсеять невалид. Решение через стек элегантнее конечно, т.к. нет необходимости обрабатывать всю строку.

[andreibudnik]

Занимаюсь недавно. Сделал без использования объектов. Не знал про понятие "стека". Использовал только for, if и function. Функция ищет соседние скобки одного вида и разного направления, если находит - вырезает их через splice, увеличивает счетчик (счетчик использую как условие выхода из цикла) и заново вызывает себя.

function validBraces(braces) {
let arr = braces.split('');
let ciclCounter = 0;
const endOfCicl = arr.length;
function recursDelBrasket(arr) {
for (let i = 0; i < arr.length; i++) {
const element = arr[i];
console.log(arr);
console.log(element);
if(arr.length === 0){
break;
}
if((element === '(') && ((i + 1) === arr.indexOf(')'))){
ciclCounter++;
arr.splice(i, 2);
return recursDelBrasket(arr);
}
if((element === '{') && ((i + 1) === arr.indexOf('}'))){
ciclCounter++;
arr.splice(i, 2);
return recursDelBrasket(arr);
}
if((element === '[') && ((i + 1) === arr.indexOf(']'))){
ciclCounter++;
arr.splice(i, 2);
return recursDelBrasket(arr);
}
if(ciclCounter >= endOfCicl){
break
}
}
}
recursDelBrasket(arr);
if(arr.length === 0) {
return true;
} else {
return false;
}
}

[yarikmen]

Спасибо за труды.
Ваше решение на Java:
import java.util.HashMap;
import java.util.Stack;
public class ValidParentheses {
public static void main(String[] args) {
String s1 = "()"; // true
String s2 = "()[]{}"; // true
String s3 = "(]"; // false
String s4 = "([)]"; // false
String s5 = "{([])}"; // true
String test = "([{(})])";





}

private static boolean isValid(String str) {
Stack<Character> stack = new Stack<>();
HashMap<Character, Character> brackets = new HashMap<>(3);
brackets.put(')', '(');
brackets.put('}', '{');
brackets.put(']', '[');

for (int i = 0; i < str.length(); i++) {
char current = str.charAt(i);
if (isClosed(current)) { // Закрывающиеся скобки
if (brackets.get(current) != stack.pop()) { // ")" => "("
return false;
}
} else { // Открывающиеся скобки
stack.push(current); } }

return stack.empty(); }

private static boolean isClosed(char chr) {
char[] c = {'}', ')', ']'};

for (int i = 0; i < c.length; i++) {
if (c[i] == chr) return true;
}
return false; } }

[ggaltqq]

Где-то читал( уже не вспомню), что в именованиях лучше не использовать прошедшее время( если только домен этого не требует). И фонетически "isClosingBracket" звучит лучше. И спасибо за видосы)

[MrTheDanils]

Сергей, контент отличный! Единственный вот момент который смутил: то, что внутри цикла, есть indexof. В итоге данная реализация ведь O(n*n)? Либо я чего то не понимаю…

[daniilzotov]

мне кажется без стека вполне можно обойтись :
алгоритм простой -
следующая скобка является ли закрывающей -
да - вырежи их и проверь еще раз предыдущую

let

function convert(str){
switch (str) {
case ')' : return '(';
case ']' : return '[';
case '}' : return '{';
default : return ' '
}
}

let test =function(arr){
if (arr.length%2 !=0) {return false}; // можно исключить

for (let i=0; i<arr.length;i++){
if (arr[i]==convert(arr[i+1])) { //является ли следующая скобочка - закрывающей?
arr=arr.slice(0, i)+arr.slice(i+2); //вырезаем обе скобочки
i=i-2; //возвращаемся к предыдущей скобочке
};
}
if (arr.length==0) {return true} else {return false};
}

console.log(arr1, test(arr1));

[lunik]

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

[Parcker]

На codwars наткнулся на эту задачу, а сегодня случайно здесь увидел.

[denyslinetskyi]

LeetCode или CodeWars - Что посоветуете для начинающих?)

[falconeye]

Thank you so much Sergey for your work! Would be great to watch your video about different data structures.