Plan to work on the hard level algorithm called "Remove Invalid Parentheses". Spent over 2 hours to study the leetcode discussion, and figured out what to work on. The most important is to write code using other people's ideas, Julia found one person to summarize the solutions through the discussion. Julia likes to apply Terse, Expressive, and Do one thing (TED) principle she learned through pluralsight.com course clean code. She likes to go over the handout of the course and apply some notes to her practice. The handout link is here.
Three code principles are outlined in the article called "3 Core Principles to Write Clean Code".
Depth first search I
1. Plan to study Java solution provided by a Google engineer first. Here is the link.
Spent over 2 hours to study the code, Julia wrote one with three test cases. Here is her C# code. Use readable function name, C# code is here.
Depth first search II
2. Plan to study Java solution provided by dietpepsi. Here is the link.
Spent over 2 hours to study the code, Julia wrote one with three test case. Here is her C# code.
The design idea is to scan the string twice, first scan is to remove the invalid ')'; then reverse the string with removed invalid ')', in other words, scan right to left virtually; this time is to remove invalid '('.
After removing invalid ')' and '(', reverse the search and then add to valid strings list.
Breadth first search ( no pruning )
Plan to study the discussion, the link is here.
C# practice code is here.
Breadth first search ( pruning )
Plan to study the BFS solution written in Java. The link is here.
A few ideas are applied to prune the BFS algorithm.
Julia's C# practice is here.
4. Plan to read this review of all solutions. The discussion link is here.
5. Plan to study the analysis written in Chinese:
对于一个字符串，在任何时候如果 ')' 的个数多于左括号，则说明从开始到现在位置必然可以删除一个')'．而这段子串可能包含多个')'，删除哪一个呢？当然删除任何一个都可以．
例如对于()())()，从开头到 s[4] 位置构成的子串多了一个右括号，因此我们需要删掉一个，而这个子串有三个右括号，但是只会产生２个结果，也就是会有一个重复值．所以在删除括号的时候，为保证不会产生重复值，需要记录一个最后删除的位置，这样可以使得在接下来删除的时候只删除这个位置之后的值．这样我们可以使得当前这一段子串不再包含多余的右括号了．这样我们可以删除了一个右括号之后合法的子串与后面还没有检查过的子串组成一个新的字符串重新开始检查．直到不再含有非法的右括号．
但是还有一种情况是包含了多余的左括号，一种直观的方法是从右向左再按照上面的方法处理一遍左括号．但是将数组逆置之后就可以重用上面的算法了．
所以总的思路就是先对字符串进行处理使得其不再含有非法右括号，然后将其翻转以后再检查是否含有非法的左括号．最后左右括号都检查完之后都合法就是我们要的答案了．
时间复杂度应该是O(n^2).
No comments:
Post a Comment