Допустимые скобки
Строки, стеки
Задача:
Учитывая строку s
, содержащую только круглые скобки (
, )
, {
, }
, [
и ]
, определите, допустимы ли скобки.
Мыслительный процесс:
Допустимой строкой круглых скобок является строка, в которой каждой открывающей скобке соответствует соответствующая закрывающая скобка того же типа. Например, строка «(()[])» допустима, а строка «(())» — нет.
Решение:
В следующем решении для решения проблемы используется стек. В стеке хранятся открытые, но еще не закрытые круглые скобки. Мы перебираем строку и для каждого символа делаем следующее:
- Если символ является открывающей скобкой, мы помещаем его в стек.
- Если символ представляет собой закрывающую скобку, мы извлекаем верхний элемент стека. Если вытолкнутый элемент не соответствует открывающей скобке закрывающей скобки, то строка недействительна.
- Если мы достигли конца строки, а в стеке еще есть элементы, то строка недействительна.
/** * @param {string} s * @return {boolean} */ function compareChar(topElement, c){ return (topElement == '{' && c == '}') || (topElement == '(' && c == ')') || (topElement == '[' && c == ']') } var isValid = function(s) { let arr = [], n = s.length; for(let i = 0; i < n; i++){ let c = s.charAt(i); if(c == '{' || c == '(' || c == '['){ arr.unshift(c); }else{ let topElement = arr.shift(); if(compareChar(topElement, c)){ continue; } arr.unshift(topElement); arr.unshift(c); } } return arr.length == 0; };
Примеры тестовых случаев:
- Ввод: s = «()»
- Вывод: правда
- Объяснение: Круглые скобки в строке совпадают, поэтому строка действительна.
- Ввод: s = «()[]{}»
- Вывод: правда
- Объяснение: Круглые скобки в строке совпадают, поэтому строка действительна.
- Ввод: s = «(]»
- Вывод: ложь
- Объяснение: Строка содержит закрывающую скобку без соответствующей открывающей скобки, поэтому строка недействительна.
Сложность времени и пространства:
Время: O(N) где N — длина строки
Пробел: O(~N) где строка содержит все открытые скобки
Я надеюсь, что этот пост в блоге был полезен!