dailylog 02-15-21

Return Valid Parens

OK kitties!

You’re given a set of parentheses and we need to check if they are valid or not. So here, I’ve laid out all the parens for you.

First, let’s look at a basic example. Left and right. This is a complete set. This is a valid set. One left, to open, one right, to close. This counts as two.

Let’s look at adding another set of valid parens. So we have ()(). This is one left, one right. followed by one left and one right. How can we check to see if this is valid? Should we first check left and then right, call it done, and then proceed to the next one? Does this sound like “checking if valid” should be a function? Possibly!

What happens if we have ()(()

For THIS particular parenthese problem, we should have a check_if_valid function that takes in n and n-1.

So for this example, we get to our first two, n and n-1 (n starts at one for this) We feed n and n-w into our check_if_valid function

Check_if_valid(n_idx, n_idx-1): if array[n_idx] == “)” and array[n_idx-1] == “(“: return True

else return False

When we return true, we need to be keeping track of our “Streak” – that is, our streak of “valid parens” – When re return false, we need to somehow “stop” our streak counting. And we will replace whatever “max” we have with our current count, if our current count is greater than the max.

I feel like I’ve gotten a little bit too high level for us kittens so lets back track. If I give you ()()()()() in a row, it gets tedious looking at each “set” and doing the mental gymnastics to see if that “set” is valid. Why don’t we employ an additional cat whose ONLY job is to look at two things and tell us if those things are (). Let’s call this cat Frank.

Ok, great.

So all you, main cat, have to do is count two and every two you send to Frank and every time Franks sends back “valid” you add a little tally to your “count of valid parentheses. How does that sound?

So in this case, we’d send frank () and he’d send True and we’d add one to our count. We’d send frank the next two, in this case () again, and he’d send back True again and we’d add an additional 1 to our count. We’d send frank the NEXT two, in this case () again, and he’d send back True again and we’d add an additional 1 to our count. We’d keep doing this and eventually we’d get 5 because all are valid parentheses.

What happens though if Frank gets )? Or if Frank gets “)(“ ? Should we be sending frank a string instead of specific things? This is something to potentially consider.

Let’s try this with an example.

())()()() So we’d send () to Frank and he’d send back Valid and we’d mark 1 on our count. and we’d add 2 to N. We’d then send Frank )( and he’d return False. We’d add 1 to N

0 1 2 3 4 5 6 ( ) ) ( ) ( )

OK this is helpful, yes?

So if we start with n_idx= 1, we pass Frank (ARRAY[n_idx], array[n_idx-1]) which would be ( and ) And Frank would pass back “VALID” and we would then increment n_idx by two n_idx=3 ANd we would send Frank (ARRAY[n_idx],ARRAY[n_idx-1]) Which would be ) ( and Frank would pass back FALSE and we would increment n_idx by 1 so n_idx=4 we would ALSO clear our counter because we broke our streak AND if our counter is greater than current_max, we would make current_max our counter. So we’d send frank (ARRAY[n_idx], ARRAY[n_idx-1]) And that would be ( and ) and Frank would send back Valid and we’d start our counter again anew

–

Am I missing anything? What happens when we receive an empty array? We don’t pass anything to frank and we return 0. What happens when we receive array length one? Well, that is invalid so we return 0. What happens if we receive a string of only ((((((( then we pass (( to frank and he returns INVALID and we return ((( to frank and he returns INVALID and then eventually we get to the end of the string… when n_idx == string.length -1 and then we can return our count, which has never been incremented. So we return zero.