Published
Edited
Nov 6, 2019
tests = [
{
input: "()())()",
output: ["()()()", "(())()"]
},
{
input: "(a)())()",
output: ["(a)()()", "(a())()"]
},
{
input: ")(",
output: [""]
}
]
removeInvalidParensBFS = (s) => {
let queue = new Set([s])
while(queue.size) {
const next = new Set()
for (let v of queue) {
if (isValid(v)) {
return [...queue].filter(isValid)
}
// otherwise invalid queue item
for (let i = 0; i < v.length; i++) {
next.add(v.slice(0, i) + v.slice(i + 1))
}
}
queue = next
}
return ['']
}
isValid = str => {
let balance = 0
for (let ch of str) {
if (ch === '(') {
balance++
} else if (ch === ')') {
balance--
}
if (balance < 0) {
return false
}
}
return balance === 0
}
removeInvalidParensBFS(tests[0].input)
md`## Complexity Analysis: Backtracking
### Time Complexity: O(2^N)
- Worse case: string contains only closing parens
- Two options for each of N parens
### Space Complexity: O(N)
_ Recursive solutions alwys uses stack space, since internal function states are saved
- Maxiumum depth of recursion decides stack space used
- One character processed at a time, base case is all characters processed
`
md`## Complexity Analysis: Limited Backtracking
### Time Complexity:
- Pruning, varies between test cases, worst case still O(2^N)
- Find number of misplaced parens
- Avoid removing and validating each by establishing upfront the valid expression length and number of left and right parens to remove, the misplaced parens
### Space Complexity:
- Max recursion depth N before hitting base case, still O(N)
`
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
