Leetcode discuss: Leetcode 10: regular expression

Here is the link.

Case study: dynamic programming solution on January 26, 2018

July 2, 2020
My practice was on January 26, 2018. Here is my blog to document my experience.

Case study
It is a good idea to work on a simple test case, and then build a table to calculate the value of regular expression matching.

I like to share the table I prepared on my blog in 2018. Here is the blog.

Test case: acd with "abc" pattern string

public class Solution {
    public bool IsMatch(string text, string pattern)
        {
            if (text == null || pattern == null) // false 
            {
                return false;
            }

            var tLength = text.Length; // 0 
            var pLength = pattern.Length; // 4

            var dp = new bool[tLength + 1, pLength + 1]; // 1, 5

            dp[0, 0] = true; // 

            for (int i = 1; i < tLength + 1; i++)
            {
                dp[i, 0] = false;
            }

            // "" matches "a*b*" etc. 
            for (int i = 1; i < pLength + 1; i++)
            {                
                dp[0, i] = i >= 2 && pattern[i - 1] == '*' && dp[0, i - 2]; 
            }

            for (int row = 1; row < tLength + 1; row++)
            {
                for (int col = 1; col < pLength + 1; col++)
                {
                    var visitChar = text[row - 1];
                    var patternChar = pattern[col - 1];

                    var isStar = patternChar == '*';
                    if (!isStar)
                    {                        
                        dp[row, col] = (patternChar == '.' || visitChar == patternChar) && dp[row - 1, col - 1];                        
                    }
                    else
                    {                                  
                        dp[row, col] = col >= 2 &&
                             // zero time
                            (( dp[row, col - 2]) ||
                             //                                                                  one time         || more than one time
                             ((pattern[col - 2] == '.' || visitChar == pattern[col - 2]) && (dp[row - 1, col - 2] || dp[row - 1, col])));
                    }

                    /*
                     * code review on May 9, 2019
                     * "mississippi"
                       "mis*is*p*."
                    else
                    {                            //   zero time          one time           more then one time        
                        dp[row, col] = col >= 2 && (dp[row, col - 2] || dp[row, col - 1] || dp[row - 1, col]);
                    } 
                     */
                }
            }

            return dp[tLength, pLength];
        }
}