Sunday, July 2, 2017

Leetcode 10 - Regular Expression Match II

July 2, 2017

Introduction


Where is the best place to find better idea for an algorithm? Julia checked the hackerrank leaderboard, but for her practice of Leetcode 10 - Regular Expression Match, she googled using keyword, "Leetcode 10 C# solution", she found one today. Here is the C# solution in the dicussion panel.

Here is the C# solution she need to study today, and the algorithm implemented is better than Julia's one. She likes to study the algorithm.


Algorithm Study


C# solution using recursive, but no timeout issue. Solution is here.


July 5, 2017

Julia worked as the mocking interviewer 35 minutes on this algorithm, she had some issue to give out clear advise on the iterative solution.

In other words, there are 3 options with string "a" and pattern "a*":

a* counts as empty, why?  because it may be "a" and "a*a"
a* counts as single a, so, next will be string "" and pattern ""
a* count  as multiple a, so next will be string "" and pattern "a*"

July 6, 2017
Continue to study a DP solution, discussion link is here.
Dynamic programming solution - practice code is here.

Read an Amazon intern story in Chinese - link is here.

Another recursive solution - Julia's most favorite one
C# practice code is here.

No comments:

Post a Comment