Your resulting code works except it doesn't handle
null gracefully. It's also more complex than it needs to be.
It is important to keep your code clean and clear. Here's a quote from the 1980 Turing Award winner's acceptance lecture:
C.A.R. Hoare, winner of the 1980 ACM Turing Award, wrote:“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”
The unit tests I gave previously were not written all at once. They were written incrementally alongside the solution code. The following is an account of how my solution evolved over the short time (few minutes) it took me to write it and the tests.
First, I handled the case for null values. I'll leave the test as an exercise for you but this is the initial code:
Next, I added the test for "()" then when that failed, implemented the solution code:
Next, I refactored to keep the code clean by introducing a variable to explain the intent of the formula,
s.length() - 1:
Then, I added another test for "", which failed with an index error. Implementing a fix, I got:
I added another assertion for "a" just for good measure but it's really a redundant assertion, given the fix.
Next, I tested for "ab()", the case where the parenthesized part is at the end and characters need to be removed from the front of the string. That failed, so I implemented a fix:
Again, I added another largely redundant assertion for "ab(c)" just to make sure I wasn't missing something.
Next, I tested for "()b", for the cases where the last character had to be recursively removed. That test failed, so I put in the fix:
This made all tests pass. In fact, I added more tests and assertions, including the general case where characters on both ends needed to be recursively removed, and they all passed immediately without failing first. This told me that my tests and code had some redundancy in it because the last
return null statement wasn't getting executed at all. Looking at lines 9, 12, and 15 above, I saw that the checks were duplicated. So, I eliminated the checks on line 9 and moved the return statement to the bottom, replacing the
return null statement with
return s.
Running the tests again, they all still passed so that confirmed those checks were indeed redundant.
On to refactoring to clean up the code again. As you can see, refactoring happens as a separate step, after you've made sure that the tests all pass.
Because I had just eliminated the statement that had used it initially, the
lastPos variable (line 7 above) now seemed oddly out of place. So, I repositioned the variable to be closer to the one other statement where it's actually used:
Not being satisfied with the readability of the last check and the explaining variable, I refactored one more time to make it more conversational:
To me, that last if-statement now reads as: "If the character at
the end of s is not ')', then recurse using the substring of s that doesn't include the character at
the end."
I run the tests again and seeing that they all still pass. Since I can't think of any other corner cases and non-redundant tests at this point, I'm done.
Note that I could have refactored some more to remove redundant tests and assertions but then felt like I needed to write some comments to explain why those test cases/assertions are missing. Recursion and reduction/degeneration is not easy to understand so I thought it better to leave the redundant code in the tests.
Hopefully, this shows you how a disciplined and systematic approach like
Test-Driven Development can improve the way you code by giving you confidence based on thorough unit testing and code cleanliness and clarity from refactoring.