Описание испытания
Учитывая строку s
, содержащую только символы '('
, ')'
, '{'
, '}'
, '['
и ']'
, определите, допустима ли входная строка.
Входная строка действительна, если:
- Открытые скобки должны быть закрыты однотипными скобками.
- Открытые скобки должны быть закрыты в правильном порядке.
- Каждой закрывающей скобке соответствует открытая скобка того же типа.
Пример 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; }