JavaScript Интервью Тест по кодированию Проблема 7

Узнайте, как определить, сбалансированы ли скобки или нет. Это реальная проблема, которую время от времени приходится решать разработчикам программного обеспечения, и многие инструменты разработки имеют собственную реализацию этой проблемы. Мы узнаем, как редактор кода может уловить наши ошибки и выделить, какие именно скобки не совпадают.
Инструкции
Если дана строка, верните true, если она содержит все сбалансированные круглые скобки () , фигурные скобки () , и квадратные скобки [].
Входные данные: Строка
Выход: Булево
Примеры
is8alanced(«(x + y) — (4)»); // -> true is8alanced(«(((10 ) (}) ((?)(:))))»); // -‘ true isBalanced(«[{()}]»); // -‘ true is8alanced(«(50)(«); // -> false
isBalanced(«[{]}»); // -‘ false
Решение

2   const openstack = [];
3   const open = '([{';
4   const close = ')]}';
5   const matches - {
6   ')': '(',
7   ']': '[',
8   '}': '{'
9   };
10
11  for (let i - 0; i ‹ str.length; i++) (
12  const char  str[i]; 13
14  // If it's an open bracket, push it into our array
15      if(open.includes(char)) (   
16      openstack.push(char);   
17          
18      // If it's a close bracket  
19      } else if(close.includes(char)) (   
20      // pop an item from the open brackets array.    
21      const lastopenBracket   openStack.pop();    
22          
23      // If the open and close bracket don't match,   return false
24      if(matches[char] !== lastopenBracket) { 
25      return false;   
26          
27      

28      

29          
30      // Ensures there are no characters left on the stack    
31      return !openStack.length;   
32  }       

Как это работает
В нашем цикле for мы обрабатываем каждый символ. Если текущий символ является открытой скобкой, мы помещаем его в наш массив openstack.
Если это не скобка, мы ничего не делаем.
Когда мы закончим обработку строки, мы должны убедиться, что у нас
что на нашем стеке не осталось открытых скобок. Если они есть, то наша строка несбалансирована.
Время
Это решение имеет временную сложность Df:
0(n).
Каждый символ обрабатывается в цикле. Внутри цикла мы выполняем только те действия, которые считаются по времени.
Пространство
Пространственная сложность составляет:
0(n).
Символы хранятся в массиве, в целом пропорциональном размеру входных данных.
Заключение
Есть много способов снять шкуру с этой кошки. Другим решением было бы иметь два указателя, один в начале и один в конце, движущиеся к середине. Они проверяли бы соответствие скобок до тех пор, пока они не встретились бы. Это также было бы o(n) решением.