Skip to content

Instantly share code, notes, and snippets.

@scottmries
Created November 16, 2023 23:14
Show Gist options
  • Save scottmries/4cfb71ed29746f089e5b4fb988a103f7 to your computer and use it in GitHub Desktop.
Save scottmries/4cfb71ed29746f089e5b4fb988a103f7 to your computer and use it in GitHub Desktop.
brackets problem recursive solution with string size reduction
const tests = [
'()[]{}',
'(((]))',
'((()))',
'](',
'(()',
'())'
]
const solutions = [
true,
false,
true,
false,
false,
false
]
const isOpening = c => {
return ['(', '{', '['].indexOf(c) > -1
}
const isClosing = c => {
return [')', '}', ']'].indexOf(c) > -1
}
const closers = {
'(': ')',
'{': '}',
'[': ']'
}
const isValid = str => {
if (str.split("").some(c => !isOpening(c) && !isClosing(c))) {
throw new Error("Chars expected to be from '(', '[', '{', ')', ']', '}'")
}
if (str.length === 0) {
return true
}
if (!isOpening(str[0])) {
return false
}
let innermostOpenerIndex = 0
while (isOpening(str[innermostOpenerIndex + 1]) ) {
innermostOpenerIndex++
}
const innermostOpener = str[innermostOpenerIndex]
const innermostCloser = str[innermostOpenerIndex + 1]
if(closers[innermostOpener] !== innermostCloser) {
return false
}
const stringWithParensRemoved = str.slice(0, innermostOpenerIndex) + str.slice(innermostOpenerIndex + 2)
return isValid(stringWithParensRemoved)
}
tests.forEach((test, i) => {
if(isValid(test) !== solutions[i]) {
throw new Error(`${test} should be ${solutions[i]}`)
}
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment