[Uber][LeetCode] Regular Expression Matching

Problem: Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

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

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

Example:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Approach: Use DP. Have a table [s.Length + 1][p.Length + 1] where table[i][j] indicates s(0..i-1) is a match of pattern p(0...j-1). Once we fill this we need to return table[s.Length][p.Length]. Here is how to fill this table - 

1. If pattern and string both are null then its a match so table[0][0] is always true.
2. If pattern is null (p.Length = 0) then its a mismatch so table[i][0] = false for i = 1...s.Length.
3. If string is null then table[0][j] can be true only if pattern has p[j - 1] = '*' and table[0, j - 2] is true for j = 1...p.Length
4. table[i][j] = table[i-1][j-1] if current pattern character i.e. p[j - 1] is either . or match with current char of string i.e. s[i-1]
5. If p[j - 1]  is '*' then
1.   a. if previous char in pattern match current char of s i.e. p[j - 2] is '.' or s[i-1] then table[i][j] = table[i][j-2] || table[i-1][j]
2. if not then table[i][j] = table[i][j-2]
6. table[i][j] = false.

Implementation in C#:

        public bool IsRegexMatch(string s, string p)

        {

            bool[,] lookup = new bool[s.Length + 1, p.Length + 1];

            lookup[0, 0] = true;

            for (int i = 1; i <= p.Length; ++i)

            {

                if (p[i - 1] == '*')

                {

                    lookup[0, i] = i - 2 >= 0 ? lookup[0, i - 2] :false;

                }

            }

            for (int i = 1; i <= s.Length; ++i)

            {

                for (int j = 1; j <= p.Length; ++j)

                {

                    if (p[j - 1] == '*')

                    {

                        lookup[i, j] = lookup[i, j - 2];

                        if (p[j - 2] == '.' || p[j - 2] == s[i - 1])

                        {

                            lookup[i, j] = lookup[i, j - 2] || lookup[i - 1, j];

                        }

                    }

                    else if (p[j - 1] == '.' || s[i - 1] == p[j - 1])

                    {

                        lookup[i, j] = lookup[i - 1, j - 1];

                    }

                    else

                    {

                        lookup[i, j] = false;

                    }

                }

            }

            return lookup[s.Length, p.Length];

        }

Complexity: O(m * n)