1. Description

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

2. Submission Details

3. Runtime Distribution

4. Example

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

5. Explaination

This problem has a typical solution using Dynamic Programming. We define the state dp[i][j] to be true if s[0..i) matches p[0..j) and false otherwise. Then the state equations are:

1. if s[i - 1] == p[j - 1] || p[j - 1] == '.'  → P[i][j] = P[i - 1][j - 1]
2. if p[j - 1] == '*'
   • if p[j - 2] != s[i - i]  → P[i][j] = P[i][j - 2], //in this case, a* only counts as empty.
   • if p[j - 2] == s[i -1] || p[j - 2] == '.'  → P[i][j] = P[i-1][j], //in this case, a* counts as multiple a.
      → or P[i][j] = P[i][j - 2] //in this case, a* counts as empty

6. Code

using Microsoft.VisualStudio.TestTools.UnitTesting;
using System.Diagnostics;

namespace Csharp.DP
{
    [TestClass]
    public class LeetCode0010
    {
        public bool IsMatch(string s, string p)
        {
            bool[,] dp = new bool[s.Length + 1, p.Length + 1];

            dp[0, 0] = true;

            for (var j = 0; j < p.Length - 1 && dp[0, j]; j += 2)
            {
                dp[0, j + 2] = p[j + 1] == '*';
            }

            for (var i = 1; i <= s.Length; i++)
            {
                for (var j = 1; j <= p.Length; j++)
                {
                    if (p[j - 1] == '*')
                    {
                        dp[i, j] = (p[j - 2] == '.' || p[j - 2] == s[i - 1]) && dp[i - 1, j] || dp[i, j - 2];
                    }
                    else
                    {
                        dp[i, j] = (p[j - 1] == '.' || p[j - 1] == s[i - 1]) && dp[i - 1, j - 1];
                    }
                }
            }
            return dp[s.Length, p.Length];
        }

        [TestMethod]
        public void Test()
        {
            Trace.WriteLine(IsMatch("aab", "c*a*b"));
        }
    }
}