Leetcode 10. Regular Expression Matching

10. RegularExpression Matching

Hard, Dynamic Programming

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 1:

Input: s = "aa", p = "a"

Output: false

Explanation: "a" does not match the entire string "aa".

Example 2:

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".

Example 3:

Input: s = "ab", p = ".*"

Output: true

Explanation: ".*" means "zero or more (*) of any character (.)".

 

Constraints:

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s contains only lowercase English letters.
• p contains only lowercase English letters, '.', and '*'.
• It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

To solve the Regular Expression Matching problem, we need to use Dynamic Programming (DP) to handle the pattern p and the string s effectively, especially considering the wildcard characters . and *.

---

Approach:

1. Dynamic Programming Table:

We define a 2D DP table dp[i][j]:

• dp[i][j] indicates whether the first i characters of s match the first j characters of p.
• Base Case:
  • dp[0][0] = true — An empty string matches an empty pattern.
  • dp[0][j] — Depends on whether p[j-1] is * and if the preceding pattern allows a match.
• Transition:
  • If p[j-1] is a regular character or .:
    • dp[i][j] = dp[i-1][j-1] if s[i-1] == p[j-1] or p[j-1] == '.'.
  • If p[j-1] is *:
    • dp[i][j] = dp[i][j-2] (zero occurrence of the preceding character in p).
    • dp[i][j] = dp[i-1][j] (one or more occurrences, if s[i-1] == p[j-2] or p[j-2] == '.').

2. Algorithm:

• Construct a DP table of size (s.Length + 1) x (p.Length + 1).
• Fill the table iteratively based on the above rules.
• The result is stored in dp[s.Length][p.Length].

---

Implementation:

public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[,] dp = new bool[m + 1, n + 1];

        // Base case: empty string matches empty pattern
        dp[0, 0] = true;

        // Handle patterns with '*'
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0, j] = dp[0, j - 2]; // '*' acts as zero occurrences
            }
        }

        // Fill the DP table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == s[i - 1] || p[j - 1] == '.') {
                    dp[i, j] = dp[i - 1, j - 1];
                } else if (p[j - 1] == '*') {
                    // '*' acts as zero occurrences or one/more occurrences
                    dp[i, j] = dp[i, j - 2] || 
                               (dp[i - 1, j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                }
            }
        }

        // The result is in the bottom-right cell of the table
        return dp[m, n];
    }
}

---

Explanation of Code:

1. Initialization:

   • dp[0][0] is true because an empty string matches an empty pattern.
   • For patterns like a*, a*b*, etc., set dp[0][j] based on whether * can eliminate its preceding character.

2. Filling the Table:

   • Match characters directly if they are the same or if the pattern has ..
   • Handle * by either ignoring the preceding character (dp[i][j-2]) or using it (dp[i-1][j]).

3. Result:

   • The result is found in dp[s.Length][p.Length].

---

Complexity Analysis:

1. Time Complexity:

   • $O(m \times n)$, where $m = s.Length$ and $n = p.Length$.

2. Space Complexity:

   • $O(m \times n)$ for the DP table.
   • Can be optimized to $O(n)$ using a rolling array.

---

Example Outputs:

Example 1:

• Input: s = "aa", p = "a"
• Output: false

Example 2:

• Input: s = "aa", p = "a*"
• Output: true

Example 3:

• Input: s = "ab", p = ".*"
• Output: true

Example 4:

• Input: s = "mississippi", p = "mis*is*p*."
• Output: false

This solution ensures correctness for all edge cases and adheres to the problem's constraints.