Leetcode 10: regular expression matching algorithm

Feb. 11, 2018

Introduction

It is 10:00 AM mock interview. I had to work on the algorithm of hard level, Leetcode 10: regular expression matching algorithm. I told that it is not easy to write in 30 minutes, I did exactly 30 minutes, wrote analysis and also wrote the code, fixed the index-out-of-range error, and then passed all test cases.

Mock interview 

I wish that the mock interview platform has some recordings like interviewing.io so I can replay how I did less than five minutes to go over the test case and explained my approach.

I just quickly pasted the analysis I did in mock interview here. And then I will write a few sentences to match my presentation in the mocking interview.

Add caption

What I did is to go over the example with text string "acd" and pattern string "ab*c", and then drew a matrix with text string and pattern string. I did not make the choice, and by accident, I chose the pattern string in the right top corner, and then it is to go over each pattern char from left to right in the row. And also I explained to the peer that I will go over the base case first, which are first row and first column. After that I will go over each row and then I did go over the row on line 72, using text "a" and compare to each pattern string and fill the value with True or False.

Specially I explained the case with text "a" and pattern string "ab*", and b* will apply zero time. So the result should be true. T(0) is the symbol whereas 0 stands for pattern repetition number of times.

Analysis and C# code 

Here is my analysis and C# code. I explained to the peer later on how many practice I went over this algorithm, so many people in the world help me to go over the algorithm. I also watched the peers to perform the algorithm more than five times.

I still remembered that the Christmas day in 2017 a young Chinese graduate student performed the algorithm almost perfectly, I could not believe that he could do it perfectly in front of my eyes, I did go through several times with experienced programmers in the world, how they struggled to write recursive function multiple times. I did ask a lot of questions.

Just two days ago, the peer shared me the news he joined LinkedIn as an intern through the wechat. It is a side story. But I just wrote down to remind myself that teaching and learning is so efficient and once I know that a young graduate student can perform, I believe that one day I also can perform as well.