Leetcode 10 - regular expression match - dynamic programming code study

Leetcode10_regularExpressionMatch_dp.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode10_regularExpressionMatch_DPSolution
{
    /// <summary>
    /// Leetcode 10 - regular expression match 
    /// Discussion code reference:
    /// https://discuss.leetcode.com/topic/6183/my-concise-recursive-and-dp-solutions-with-full-explanation-in-c
    /// 
    /// review the dynamic programming solution later 
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
        }

        /**
        * f[i][j]: if s[0..i-1] matches p[0..j-1]
        * if p[j - 1] != '*'
        *      f[i][j] = f[i - 1][j - 1] && s[i - 1] == p[j - 1]
        * if p[j - 1] == '*', denote p[j - 2] with x
        *      f[i][j] is true iff any of the following is true
        *      1) "x*" repeats 0 time and matches empty: f[i][j - 2]
        *      2) "x*" repeats >= 1 times and matches "x*x": s[i - 1] == x && f[i - 1][j]
        * '.' matches any single character
        */
        bool isMatch(string s, string p) {            
            int m = s.Length, n = p.Length;

            var f = new bool[m + 1][];

            for (int i = 0; i < m + 1; i++)
            {
                f[i] = new bool[n + 1]; 
            }                
        
            f[0][0] = true;

            for (int i = 1; i <= m; i++)
            {
                f[i][0] = false;
            }

            // p[0.., j - 3, j - 2, j - 1] matches empty iff p[j - 1] is '*' and p[0..j - 3] matches empty
            for (int j = 1; j <= n; j++)
            {
                f[0][j] = j > 1 && '*' == p[j - 1] && f[0][j - 2];
            }

            for (int i = 1; i <= m; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (p[j - 1] != '*')
                    {
                        f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || '.' == p[j - 1]);
                    }
                    else
                    {
                        // p[0] cannot be '*' so no need to check "j > 1" here
                        f[i][j] = f[i][j - 2] || (s[i - 1] == p[j - 2] || '.' == p[j - 2]) && f[i - 1][j];
                    }
                }
            }
        
            return f[m][n];
        }
    }
}