Leetcode 10 - Regular Expression Matching

July 2, 2017

Introduction

It takes a lot of practice to learn one of the hard algorithm on Leetcode. Leetcode 10 regular expression matching's problem statement is here.

Algorithm Practice

Julia practiced the algorithm more than five times in last three months, she wrote more than two times in her practice as an interviewee, and then she mocked interview more than three people to work on the algorithm.

One of best codes is here written in Ruby, Julia met a very experienced programmer and then learned a few things. The code is here. Julia will write it using C#, and then try to run against Leetcode 10 online judge and see how many things are missing.

July 2, 2017 2:48 pm
Julia spent 40 minutes to work on C#, and the code is working except timeout issue. C# code is here.

Memoization Solution

One of the solutions is to use memoization to solve the problem. 

3:02 pm, Julia added memo as a Dictionary<string, bool>, to simplify the problem, assuming that " " is not used in regular expression matching, the code passes all test cases.

C# code is here.

No Memo Solution 

Julia could not figure out the solution by herself, so she googled and then came cross this solution through Leetcode discussion. C# code is here.  Leetcode discuss link is here. She wrote a blog about the solution, link is here.

July 6, 2017

One more recursive solution without using memo is here.

Problem solving

July 2, 2017 2:48 pm
Julia spent 40 minutes to work on C#, and the code is working except timeout issue. C# code is here.

July 6, 2017

To solve timeout issue, it is to early return the recursive tree, do not go over every node of tree.

Here is the C# code.

It is a brutal truth, Julia is not ready to be a professional interviewer or expert on algorithm. She could not spot the timeout bug in the code. She took more than 4 days and then figure out the bug. Right side is the C# code written in July 2 with a timeout bug, left side is the bug-free code.

The return statement with the format of "return A || B" will not run B if A is true. In other words, "return A || B" is not the same as
bool result = A; 
result |=  B;
The above solution to separate in two statements will cause timeout, since every branch of recursive tree will be executed. It is a fatal bug.

Inspired by the short and clean code, Julia continued to make the C# code short and clean. C# code is here.

One more step to simplify the code, code is here.

Summary 

It is so exciting to learn a hard algorithm through so many practice and code review. Julia worked with over 5 peers to solve the algorithm, she also wrote more than 5 times. Through the journal of the practice, she is able to track her progress and learn to solve the problem.

It is so much fun once the timeout bug is found through online judge on July 2. Julia kept reading more solutions until she found out the real issue - subtle bug in the writing.