Leetcode 10 - regular expression match - play with dynamic programming - 4 test cases

Leetcode10_regularExpressionMatch_dynamicProgramming.cs

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

namespace Leetcode10_RegularExpressionMatch
{
    /// source code reference:
    /// https://discuss.leetcode.com/topic/40371/easy-dp-java-solution-with-detailed-explanation
    /// July 6, 2017
    /*
    Here are some conditions to figure out, then the logic can be very straightforward.
    1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
    2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
    3, If p.charAt(j) == '*': 
    here are two sub conditions:
        1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  
            // in this case, a* only counts as empty
        2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
               dp[i][j] = dp[i-1][j]    // in this case, a* counts as multiple a 
            or dp[i][j] = dp[i][j-1]    // in this case, a* counts as single a
            or dp[i][j] = dp[i][j-2]    // in this case, a* counts as empty
    */
    class Program
    {
        static void Main(string[] args)
        {
           // RunTestcase1();
           // RunTestcase2();
            RunTestcase3(); 
           //   RunTestcase4(); 
        }

        public static void RunTestcase1()
        {
            bool result = isMatch("aa","a*"); // a* counts as multiple a
        }

        public static void RunTestcase2()
        {
            bool result = isMatch("a", "a*");
        }

        public static void RunTestcase3()
        {
            bool result = isMatch("a", "a*a");
        }

        public static void RunTestcase4()
        {
            bool result = isMatch("", "a*b*c*");
            Debug.Assert(result);
        }
        /// <summary>
        /// 
        /// </summary>
        /// <param name="s"></param>
        /// <param name="p"></param>
        /// <returns></returns>
        public static bool isMatch(String s, String p)
        {
            if (s == null || p == null)
            {
                return false;
            }

            var length = s.Length;
            var lengthP = p.Length;

            var dp = new bool[s.Length + 1][];

            for (int i = 0; i < s.Length + 1; i++)
            {
                dp[i] = new bool[lengthP + 1];
            }

            dp[0][0] = true;

            //"" matches "a*" and "a*b*" and "a*b*b*" etc. 
            //dp[0][i] = 1, first dimension 0 means that string is empty
            //second dimension i, 2, 4, 6, dp[0][i] = true
            for (int i = 0; i < lengthP; i++)
            {
                if (p[i] == '*' && dp[0][i - 1])
                {
                    dp[0][i + 1] = true;
                }
            }

            for (int i = 0; i < length; i++)
            {
                var visit = s[i];

                for (int j = 0; j < lengthP; j++)
                {
                    var pattern = p[j];

                    var upperLeft = dp[i][j]; 
                    var upper = dp[i][j + 1]; // multiple a
                    var left  = dp[i + 1][j];

                    var current = false; // work on dp[i+1][j+1]

                    if (pattern == '.' || pattern == visit)
                    {
                        current = upperLeft;
                    }                   

                    if (pattern == '*')
                    {
                        var previous = p[j - 1]; // assuming that j - 1 > 0

                        var skipLastTwo = dp[i + 1][j - 1]; // a* count as empty

                        if (previous != visit && previous != '.')
                        {
                            current = skipLastTwo; // a* count as empty
                        }
                        else
                        {
                            current = (left || upper || skipLastTwo);
                        }
                    }

                    dp[i + 1][j + 1] = current;
                }
            }

            return dp[length][lengthP];
        }
    }
}