Grind 75. Valid Parentheses (2/75) 

Статья-решение второй задачи из списка для подготовки к IT собеседованиям Grind 75.

На вход подается строка s состоящая из символов '(', ')', '{', '}', '[' или ']'

Необходимо проверить, является ли строка валидной.

Строка является валидной, если соответствует следующим пунктам:

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

Примеры:

Пример 1:
Input: s = "()"
Output: true

Пример 2:
Input: s = "()[]{}"
Output: true

Пример 3:
Input: s = "(]"
Output: false

Для решение данной задачи мы будем использовать структуру данных Stack, про нее можете прочитать тут.

Алгоритм для решения задачи будет следующим:

Сначала мы проверим, что длина строки больше одного символа. Затем мы объявим стек в виде массива и хеш-таблицу в виде закрытых скобок как ключей и открытых скобок как значений. Смысл в том, что мы будем проверять каждый символ строки. Если он будет равняться открытой скобке, то мы будем добавлять его в наш стек. Если нет, то мы будем проверять, является ли последний элемент нашего стека противоположным элементом закрытой скобке по типу. Если да, то мы удалим последний элемент с помощью правила "Последним пришел - Первым вышел". Все это позволит нам проверить, правильно ли сбалансирована строка. Если в конце стек будет пустым, значит все элементы были в правильном порядке.

Теперь приступим к реализации нашего алгоритма:

1) Создадим функцию isValid с одним параметром s, которая будет проверять переданную строку.

const isValid = (s) => {
 // code
}

2) После объявления функции в условии if проверим длину строки s. Если длина меньше или равна 1, то возвращаем false, так как строка с одной или менее символов не может быть сбалансированной, потому что у каждой открывающей скобки должна быть закрывающая.

if (s.length <= 1) return false

3) Объявим массив, который будет играть роль стека.

const stack = []

4) Объявим хэш-таблицу с ключами в виде закрытых скобок и значениями в виде открытых.

const braces = {
  ')': '(',
  ']': '[',
  '}': '{'
}

5) Запустим цикл for of, в котором переберем все символы char в переданной строке s.

for (let char of s) {
 // code
}

6) Внутри цикла проверим, является ли char открывающей скобкой. Если да, то она добавляется в стек.

for (let char of s) {
  if (!braces[char]) {
    stack.push(char) 
  } else {
    // code
  }
}

7) Если char не является открывающей скобкой, то выполняется код в блоке else.

8) В блоке else проверим, соответствует ли последний элемент стека открывающей скобке для текущей закрывающей скобки char. Если да, то последний элемент удаляется из стека с помощью метода pop().

for (let char of s) {
  if (!braces[char]) {
    stack.push(char) 
  } else {
    if (stack[stack.length - 1] === braces[char]) {
      stack.pop()
    } else {
      // code
    }
  }
}

9) Если последний элемент стека не соответствует открывающей скобке для текущей закрывающей скобки, то возвращается false, так как скобки не сбалансированы.

for (let char of s) {
  if (!braces[char]) {
    stack.push(char) 
  } else {
    if (stack[stack.length - 1] === braces[char]) {
      stack.pop()
    } else {
      return false
    }
  }
}

10) По окончании цикла проверяем длину стека. Если она равна 0, то все скобки сбалансированы и возвращаем true. Если же длина стека не равна 0, то скобки не сбалансированы и возвращаем false.

Полный код функции:

const isValid = (s) => {
  if (s.length <= 1) return false
   
  const stack = []
  const braces = {
    ')': '(',
    ']': '[',
    '}': '{'
  }
   
  for (let char of s) {
    if (!braces[char]) {
      stack.push(char) 
    } else {
      if (stack[stack.length - 1] === braces[char]) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  
  return stack.length === 0
}

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

Решение так же является оптимальным, что доказывает скорость выполнения.

Подписывайтесь на мой канал, в нем будут новые разборы и интересные статьи:)