Timeline for How can you find all unbalanced parens in a string in linear time with constant memory?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 16, 2020 at 10:30 | history | edited | CommunityBot |
Commonmark migration
|
|
| Jan 18, 2019 at 14:33 | history | edited | John L. | CC BY-SA 4.0 |
Simpler notation for iteration index. Added link to code.
|
| Jan 18, 2019 at 12:13 | comment | added | dquijada | Took me a bit to understand this, but I like it, it's pretty clever.. and works at least for every case I have thought | |
| Jan 18, 2019 at 12:09 | comment | added | John L. | @OzrenTkalcecKrznaric Exactly because $p+1$ falls outside of the boundary, there is no unbalanced opening parentheses in "())". | |
| Jan 18, 2019 at 12:04 | history | edited | John L. | CC BY-SA 4.0 |
Better explanation. Fixed typos.
|
| Jan 18, 2019 at 9:06 | comment | added | OzrenTkalcecKrznaric | Finding unbalanced opening parentheses is incorrect. I.e. if your arr is "())", p is 2 and p+1 falls outside of the arr boundary. Just an idea - to find unbalanced opening parentheses you could reverse arr and use part of algorithm to find unbalanced closing parentheses (of course, with reversely adapted indexes). | |
| Jan 18, 2019 at 7:35 | comment | added | John L. | It looks like I missed the rather obvious but most important explanation. The logic is, in fact, very simple. First, we output each extra opening parenthesis. Once we have passed the turning point, we output each extra closing parenthesis. Done. | |
| Jan 18, 2019 at 7:24 | history | edited | John L. | CC BY-SA 4.0 |
Fixed some typos.
|
| Jan 18, 2019 at 7:09 | comment | added | temporary_user_name | Lol, exercise 1 and problem 1, cute. The logic of the algorithm you've described is surprisingly hard to visualize. I would have to code this out tomorrow to get it. | |
| Jan 18, 2019 at 6:53 | history | answered | John L. | CC BY-SA 4.0 |