Практика

Тут мы обсудим порядок решения задачи.

Любая задача требует моделирования. Оно состоит из:

1. Получения задачи;
2. Построения абстрактной модели - мозговой штурм;
3. Реализация задачи;
4. Тестирование решения и его улучшение;
5. Дополнительные пояснения.

Мы не будем проходиться по всем этапам. Но отметим, что в дальнейшем будем стараться решать все задачи, предварительно проходя через первые 3 пункта.

Ссылка на задачу

Valid Parentheses

Описание задачи

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.
• Every close bracket has a corresponding open bracket of the same type.

Примеры

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Ограничения

1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.

Построение абстрактной модели

Тут возможны 2 пути - первый путь это написание псевдокода, второй путь это пошаговое описание процесса решения.

Псевдокод

инициализировать пустой стек
создать сопоставление открывающих скобок с соответствующими закрывающими

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

после итерации проверить, пуст ли стек
вернуть true, если стек пуст, иначе вернуть false

Пошаговое описание

1. Инициализируем пустой стек.
2. Создаём объект для сопоставления открывающих скобок с соответствующими закрывающими.
3. Проходим по каждому символу строки:
   • Если символ является открывающей скобкой, добавляем его в стек.
   • Если символ является закрывающей скобкой, извлекаем верхний элемент из стека и проверяем соответствие.
4. После итерации проверяем, пуст ли стек.
5. Возвращаем true, если стек пуст, иначе возвращаем false.

Реализация задачи

function isBalanced(s) {
  let stack = [];
  let obj = {
    "(": ")",
    "[": "]",
    "{": "}",
  };

  for (let i = 0; i < s.length; i++) {
    let char = s[i];

    if (obj[char]) {
      stack.push(char);
    } else {
      let top = stack.pop();
      if (obj[top] !== char) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

Пошаговая визуализация

Решение задачи может быть трудным, но понимание каждого шага на каждом этапе заметно упрощает сложность.

Внимание

На видео ниже контекст функции описан очень условно. В действительности он намного сложнее. Но детальное рассмотрение его элементов и его работы не является целью данного курса. Прошу вас просто принять это как условность, для упрощения понимания самого алгоритма.