Посещавам уебсайта LeetCode много често, за да практикувам решаване на въпроси относно структурата на данните и алгоритмите и да подобря уменията си за кодиране. Валидни скоби е един от класическите въпроси за интервю и аз ще споделя моето решение с вас в тази публикация. Ето го въпроса:

При даден низ, съдържащ само знаците '(', ')', '{', '}', '[' и ']', определете дали въведеният низ е валиден.

Въведен низ е валиден, ако:

Отворените скоби трябва да се затварят от същия тип скоби.

Отворените скоби трябва да бъдат затворени в правилния ред.

Имайте предвид, че празен низ също се счита за валиден.

Има много начини за решаване на този проблем, но моят подход ще бъде да внедря stack. stack е структура от данни, която обработва отвън навътре чрез използване на две основни операции; push за добавяне на елемент в горната част на колекция и pop за премахване на елемента от горната част на колекцията. Нека изброим основните стъпки за решаване на проблема:

  1. Дефинирайте стек, който е масив.
  2. Преминете през всеки елемент в даден низ.
  3. Ако елементът е отваряща скоба („(“ или „{“ или „[“), натиснете го в стека.
  4. Ако елементът е затваряща скоба (')' или '}' или ']'), отделете последния елемент от стека само ако съвпада с срещнатата затваряща скоба и продължавайте да итерирате през низа. Ако затварящата скоба не съвпада с отварящата скоба, поставена отгоре на стека, излезте от цикъла и върнете false, защото скобите в низа не са балансирани.
  5. Ако стекът е празен след пълно повторение на низа, върнете true, защото скобите в низа са балансирани и имате валиден низ.

По-долу е моят код в JavaScript:

Ако искаме да преработим този код, hash ще бъде добра опция за използване. По-долу е създадена „карта“ за идентифициране на двойките; затварящите скоби са свързани със съответните им отварящи скоби. Когато срещната затваряща скоба в низа съвпадне с една от идентифицираните keys на „карта“, съответните value ще бъдат премахнати от върха на стека. Ако има несъответствие, ще върне false.

Това са двата начина, които намерих за решаване на този проблем, но вярвам, че има много повече различни подходи за решаване на това предизвикателство. Благодаря, че прочетохте, надявам се, че публикацията ми е полезна.