parentheses scoring?
· 2 min read
todays daily was another parenthesis question, but this time I had quite a bit of trouble with coming up with the solution.
there isn't really a brute force idea here, when looking at this question. there's no good way of measuring depth.
and that was my first issue, I thought that depth was this major part of the question. I don't think that's unusual, it seems natural to imagine depth to have some sort of relevance given we are getting deeper into the brakcets
so with this depth idea in mind, I imagine there is some kind of combo system? every time there is a right bracket ( I would increase the depth, while every time there is a ) I would decrease it.
and it works on a few examples but it breaks apart very easily. i can't recall exactly what I was trying but it seems like I would be imagining something like when the bracket closes we calculate the depth level. ( ((())) ) This is a big example that returns 8 and it breaks my idea apart. it says that at a level 4 bracket we would then add 3 on the next level then 2 before it. We would get a total value of 10.
clearly this is wrong. And I should've looked at the question again.
what I should've done instead is to imagine the question more like a recursive question, where I would've thought of base cases, rather than looking for some trick based on my intuition with these problems.
it seems like with me doing other questions like 2267. Check if There Is a Valid Parentheses String Path which has the trick of using depth, it made me think this was the same.
there is essentially 2 cases here:
- () which will return 1
- (A) which will return 2x
thats really it! if I was able to identify these base cases, then I could've have coded it up.
i did get to that idea eventually, but it felt a little weird, it felt like I was creating what I called a "bandaging solution" where it would work in this niche scenario, but that is a property of the question, not something specific.