Leetcode 10 - regular expression match - using dynamic programming - pass online judge, study one of solutions.

Leetcode10_regularExpressionMatch_DPSolution.cs

using System;
using System.Collections.Generic;
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)
        {
            bool result = isMatch("a","ab*"); 
        }

        /// <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;

            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 current = false; 
                    if (pattern == '.') 
                    {
                        current = dp[i][j];
                    }

                    if (pattern == visit) 
                    {
                        current = dp[i][j];
                    }

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

                        if (previous != visit && previous != '.') 
                        {
                            current = dp[i + 1][j - 1];
                        } 
                        else 
                        {
                            current = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1]);
                        }
                    }

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

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