Допустимые скобки

Строки, стеки

Задача:
Учитывая строку 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) где строка содержит все открытые скобки

Я надеюсь, что этот пост в блоге был полезен!