Introduction
It is hard level algorithm and I have to review the algorithm first. Most of important is that I have to understand how to write working code, and then pass online judge. I reviewed one of submissions I did more than 6 months ago.
Most of important is to write a story how to solve the problem using test case "()())()". I found this test case through my last submission. I have to explain my solution based on this test case.
Story first, code follows
I have to write a story how to work on the test case, I have to write a story. And then I need to conduct time complexity as well.
I put the story in the function specification. I reviewed the code and made some changes.
Here is the code.
Explain how I will solve the problem using test case "()())()", and the valid strings are "()()()" and "(())()".
And based on the test case, explain the time complexity of the algorithm. For example, first part of string is "()())()", second part is same string, how many valid strings we have.
Follow up
July 20, 2018
In order to figure out time complexity, I like to work on the test case with string ()())() repeating twice like ()())()()())(). How many valid string can we generate?
Based on my last practice, the string ()())() is removed extra close parathese and there are two valid strings. One is ()()() and another one is (())().
For first valid string ()()(), concatenated by ()())(), how many valid strings can be generated?
()()()()())()
When I work on the extra close paratheses, there are five options to remove ). So there are five valid strings:
(()()()())()
()(()()())()
()()(()())()
()()()(())()
()()()()()()
so in total there are 10 valid strings.
We like to find the upper bound of number of valid strings. Each substring ()())() has two valid string, but the concatenation of two generates 10 valid strings, not just 2 * 2.
I used to be math major. I like to figure out the upper bound. I do like to get more experience on a concrete example. My understanding is that I may have barrier to think clearly about the problem since I do not have any good experience on one test case.
It is time for me to build a good test case and write down some learning here.
Try to explain
There is new case to remove extra close paratheses. In the first string, two extra paratheses instead of one can be removed. We know that ()())() string at least one close parathese should be removed.
The extra user case explains there are extra 6 valid string available after concatenating two strings. There are three options to remove two close parentheses.
No comments:
Post a Comment