Описание испытания

Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, допустима ли входная строка.

Входная строка действительна, если:

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

Пример 1:

Input: s = "()"
Output: true

Пример 2:

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

Пример 3:

Input: s = "(]"
Output: false

Подход

  • Создайте пустой стек, чтобы отслеживать открывающие скобки.
  • Прокрутите каждый символ во входной строке.
  • Если символ является открывающей скобкой, поместите его в стек.
  • Если символ является закрывающей скобкой, извлеките верхний элемент из стека и проверьте, соответствует ли он соответствующим открывающим скобкам для текущих закрывающих скобок.
  • Если стек пуст и все скобки совпали, вернуть True. В противном случае вернуть False.

Интуиция

  • Ключом к решению этой проблемы является признание того, что скобки должны быть сопоставлены в правильном порядке. То есть каждая закрывающая скобка должна соответствовать самой последней открывающей скобке.
  • Мы можем использовать стек для отслеживания открывающих скобок по мере их появления во входной строке.
  • Когда мы сталкиваемся с закрывающими скобками, мы проверяем, соответствует ли верхний элемент стека соответствующим открывающим скобкам.
  • Если это так, мы извлекаем элемент из стека и продолжаем. Если это не так, круглые скобки недействительны, и мы можем немедленно вернуть False.
  • Если мы достигли конца входной строки, а стек пуст, мы знаем, что все круглые скобки были сопоставлены, и мы можем вернуть True.
  • Если стек не пуст, мы знаем, что есть открывающая скобка без соответствующей закрывающей скобки, и мы можем вернуть False.
function isValid(s: string): boolean {
  let parenthesesArray: string[] = [];
  for (let char of s) {
    if (char == "[" || char == "(" || char == "{") {
      parenthesesArray.push(char);
    } else {
      if (parenthesesArray.length === 0) {
        return false;
      }
      if (
        (char == "]" && parenthesesArray[parenthesesArray.length - 1] == "[") ||
        (char == "}" && parenthesesArray[parenthesesArray.length - 1] == "{") ||
        (char == ")" && parenthesesArray[parenthesesArray.length - 1] == "(")
      ) {
        parenthesesArray.pop();
      }
      else {
        return false;
      }
    }
  }

  return parenthesesArray.length === 0;
}