Валидные скобки: разбор задачи

Почему эта задача важна?

Задача на проверку валидности скобок позволяет оценить:

• 🧠 Понимание принципа работы стека
• ⚡ Умение эффективно обрабатывать строки
• 🎯 Способность выявлять симметричные структуры в данных
• 🐛 Навыки обработки различных краевых случаев

Постановка задачи

Формулировка:

Дана строка s, состоящая из следующих символов: '(', ')', '{', '}', '[' и ']'. Строка s является валидной, если:

1. Каждая открытая скобка закрыта скобкой того же типа.
2. Открытые скобки закрыты в правильном порядке.
3. Каждая закрытая скобка имеет соответствующую открытую скобку того же типа. Верните true, если строка s валидна, и false в противном случае.

Примеры:

// Первый пример ✅
Input: s = "()[]{}"
Output: true
Объяснение: Каждая открытая скобка закрыта скобкой того же типа в правильном порядке.

// Второй пример ❌
Input: s = "(]"
Output: false
Объяснение: Открывающая круглая скобка закрыта квадратной, что неверно.

// Третий пример ❌
Input: s = "([)]"
Output: false
Объяснение: Скобки закрыты в неправильном порядке.

// Четвертый пример ✅
Input: s = "{[]}"
Output: true
Объяснение: Вложенные скобки различных типов правильно закрыты.

Подходы к решению

Решение 1: Использование стека 📚

function isValid(s) {
  const stack = [];
  
  // Соответствие закрывающих скобок открывающим
  const brackets = {
    ')': '(',
    '}': '{',
    ']': '['
  };
  
  for (let char of s) {
    // Если символ - закрывающая скобка
    if (char in brackets) {
      // Сравниваем с последней открывающей скобкой в стеке
      const topElement = stack.pop() || '#';
      
      // Если не совпадает - последовательность невалидна
      if (topElement !== brackets[char]) {
        return false;
      }
    } else {
      // Если символ - открывающая скобка, добавляем в стек
      stack.push(char);
    }
  }
  
  // Проверяем, что стек пуст (все открывающие скобки закрыты)
  return stack.length === 0;
}

Анализ решения:

✅ Оптимальная временная сложность O(n)

✅ Оптимальная пространственная сложность O(n) в худшем случае

✅ Элегантное и интуитивно понятное решение

✅ Легко модифицировать для других типов скобок

Решение 2: Упрощенный вариант решения со стеком 🚀

function isValid(s) {
  const stack = [];
  
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    
    if (char === '(' || char === '{' || char === '[') {
      // Добавляем открывающую скобку в стек
      stack.push(char);
    } else {
      // Если стек пуст, но встретили закрывающую скобку
      if (stack.length === 0) return false;
      
      const lastBracket = stack.pop();
      
      // Проверяем соответствие типов скобок
      if (
        (char === ')' && lastBracket !== '(') ||
        (char === '}' && lastBracket !== '{') ||
        (char === ']' && lastBracket !== '[')
      ) {
        return false;
      }
    }
  }
  
  // Проверяем, что все открывающие скобки были закрыты
  return stack.length === 0;
}

Характеристики:

✅ Явная проверка каждого типа скобок

✅ Более понятный код для начинающих

✅ Те же временная и пространственная сложности O(n)

❌ Немного более многословная реализация

Решение 3: Использование строкового стека 📝

function isValid(s) {
  let stack = "";
  
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    
    if (char === '(' || char === '{' || char === '[') {
      // Добавляем открывающую скобку в строковый стек
      stack += char;
    } else {
      // Проверяем соответствие закрывающей скобки последней открывающей
      if (stack.length === 0) return false;
      
      const lastChar = stack[stack.length - 1];
      
      if (
        (char === ')' && lastChar === '(') ||
        (char === '}' && lastChar === '{') ||
        (char === ']' && lastChar === '[')
      ) {
        // Удаляем последнюю открывающую скобку из стека
        stack = stack.substring(0, stack.length - 1);
      } else {
        return false;
      }
    }
  }
  
  return stack.length === 0;
}

Преимущества и недостатки:

✅ Наглядная демонстрация принципа работы стека

✅ Не использует встроенные структуры данных (только строки)

❌ Менее эффективно из-за операций со строками

❌ Не рекомендуется для больших входных данных

Решение 4: Рекурсивное удаление парных скобок 🔄

function isValid(s) {
  // Базовый случай: пустая строка валидна
  if (s.length === 0) return true;
  
  // Если длина нечетная - точно невалидна
  if (s.length % 2 !== 0) return false;
  
  // Ищем и удаляем парные скобки
  let hasChanged = false;
  let str = s;
  
  do {
    const oldLength = str.length;
    
    // Заменяем все пары скобок на пустую строку
    str = str.replace(/\(\)|\[\]|\{\}/g, '');
    
    // Проверяем, изменилась ли строка
    hasChanged = str.length !== oldLength;
    
  } while (hasChanged && str.length > 0);
  
  // Если строка пуста, все скобки были парными
  return str.length === 0;
}

Особенности:

✅ Интересный концептуальный подход

✅ Легко понять базовую идею решения

❌ Менее эффективен из-за множественных замен в строке

❌ Временная сложность выше O(n)

Рекомендации по решению 💡

1. Выбор метода решения:

   • 🚀 Стек - оптимальный и классический инструмент для этой задачи
   • 📝 Важно помнить о порядке закрытия скобок (LIFO - Last In, First Out)
   • 🧐 При собеседовании стек почти всегда правильный ответ для этой задачи

2. Важные моменты:

   • 📝 Проверка пустой строки (пустая строка считается валидной)
   • 🔄 Проверка нечетной длины (быстрый способ отбраковать невалидные строки)
   • 🧮 Корректное сопоставление типов скобок

Распространённые ошибки

1. 🤦‍♂️ Забывание проверить, что стек пуст в конце обработки
2. 😅 Путаница при сопоставлении типов скобок
3. 🐛 Неправильная обработка случая, когда первый символ - закрывающая скобка

Оптимизации

Ранняя проверка длины строки

function isValid(s) {
  // Если длина нечетная - точно невалидна
  if (s.length % 2 !== 0) return false;
  
  const stack = [];
  const brackets = {
    ')': '(',
    '}': '{',
    ']': '['
  };
  
  for (let char of s) {
    if (char in brackets) {
      const topElement = stack.pop() || '#';
      if (topElement !== brackets[char]) {
        return false;
      }
    } else {
      stack.push(char);
    }
  }
  
  return stack.length === 0;
}

Оптимизация для частых последовательностей

function isValid(s) {
  // Если длина нечетная - точно невалидна
  if (s.length % 2 !== 0) return false;
  
  // Оптимизация для пустой строки
  if (s.length === 0) return true;
  
  // Быстрая проверка на валидные начальный и конечный символы
  const firstChar = s[0];
  const lastChar = s[s.length - 1];
  
  if (
    lastChar === '(' || 
    lastChar === '{' || 
    lastChar === '[' || 
    firstChar === ')' || 
    firstChar === '}' || 
    firstChar === ']'
  ) {
    return false;
  }
  
  const stack = [];
  const brackets = { ')': '(', '}': '{', ']': '[' };
  
  for (let char of s) {
    if (char in brackets) {
      if (stack.pop() !== brackets[char]) {
        return false;
      }
    } else {
      stack.push(char);
    }
  }
  
  return stack.length === 0;
}

Заключение

При решении задачи важно помнить:

• 🤹‍♂️ Стек является идеальной структурой данных для проверки сбалансированных скобок
• 📊 Решение со стеком имеет оптимальную сложность O(n) по времени и памяти
• 🧠 Правильная обработка различных типов скобок и их порядка закрытия - ключ к успеху

Эта задача является классической при изучении структур данных и встречается в различных вариациях на собеседованиях. Она демонстрирует важность выбора правильной структуры данных для эффективного решения проблемы. 🌟