3 ms·
The "Simple Balanced Parentheses" problem solution does not have to use a stack one index for opening(+1) and closing(-1) parentheses should be enough. Or am I
by msoad 12y ago
The "Simple Balanced Parentheses" problem solution does not have to use a stack one index for opening(+1) and closing(-1) parentheses should be enough. Or am I wrong?!
- gms7777 12y agoI believe you are correct. Instead of using a stack, you can add one for opening, subtract one for closing and as long as your count is non-negative, it will work the same way. Its effectively the same algorithm, except instead of actually keeping the stack, you're keeping track of the number of objects in the stack, and it'll reduce your worst case space requirement from linear in the number of parentheses to logarithmic.
- RadioactiveMan 12y agoIf you're working with multiple symbols, such as (), {}, and [], you'd want to use a stack. Closing a child ( before its parent { would be an error.
- msoad 12y agoYou can still use an index for each symbol and track diff of child vs. parent and make sure it's never negative.
- nitishmd 12y agoWouldn't the worst case space complexity be the same then? for eg: ( { [ ] } ) as you will be keeping index for each the symbols. Technically it can be implemented, but isn't stack a better approach?