LeetCode 10 Solution - Regular Expression Matching

Problem Statement (LeetCode 10)

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 just a substring.

Examples

Example 1

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' allows 'a' to repeat 0 or more times.

Example 2

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

Example 3

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

Constraints

• 1 <= s.length, p.length <= 20
• s contains only lowercase English letters.
• p contains only lowercase English letters, . and *.

---

Optimal Approach: Dynamic Programming (O(m * n) Time Complexity)

Intuition

• Use Dynamic Programming (DP) to break the problem into smaller subproblems.
• Define dp[i][j] as whether s[0..i-1] matches p[0..j-1].

Key Observations

1. If p[j-1] is a normal character (a-z):
   • dp[i][j] = dp[i-1][j-1] if s[i-1] == p[j-1].
2. If p[j-1] is . (matches any character):
   • dp[i][j] = dp[i-1][j-1].
3. If p[j-1] is * (zero or more of p[j-2]):
   • dp[i][j] = dp[i][j-2] (zero occurrences of p[j-2]).
   • OR dp[i][j] = dp[i-1][j] if s[i-1] == p[j-2] or p[j-2] == '.'.

---

LeetCode-Compatible C++ Code

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        
        dp[0][0] = true;  // Empty string matches empty pattern
        
        // Handle patterns with '*' that match empty string
        for (int j = 2; j <= n; j += 2) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        
        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];  // Direct match or '.' match
                } 
                else if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2];  // '*' acts as zero occurrence
                    if (p[j - 2] == s[i - 1] || p[j - 2] == '.') {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];  // '*' acts as multiple occurrences
                    }
                }
            }
        }
        
        return dp[m][n];
    }
};

---

Step-by-Step Explanation

Example 1: s = "aa", p = "a*"

Initial DP Table:
   ""  a   *
""  T   F   T
a   F   T   T
a   F   F   T

✅ Palindrome!

---

Example 2: s = "mississippi", p = "mis*is*p*."

Initial DP Table:
   ""  m  i  s  *  i  s  *  p  *  .
""  T  F  F  F  T  F  F  T  F  T  F
m   F  T  F  F  T  F  F  T  F  T  F
i   F  F  T  F  F  T  F  T  F  T  F
s   F  F  F  T  F  F  T  T  F  T  F

❌ Not a palindrome!

---

Why This Approach is Best

Approach	Time Complexity	Space Complexity	Why?
Dynamic Programming (Best)	O(m * n)	O(m * n)	Solves efficiently using memoization.
Brute Force	O(2^m)	O(m)	Exponential complexity.
Recursion with Memoization	O(m * n)	O(m * n)	Similar to DP, but harder to debug.

---

Alternative Approaches & Why Not?

1️⃣ Brute Force (Backtracking)

• Try all possible ways to match s and p.
• Problem: Exponential complexity O(2^m) → Too slow.

Code

class Solution {
public:
    bool isMatch(string s, string p) {
        return backtrack(s, p, 0, 0);
    }
    
    bool backtrack(string &s, string &p, int i, int j) {
        if (j == p.size()) return i == s.size();
        
        bool firstMatch = (i < s.size() && (s[i] == p[j] || p[j] == '.'));
        
        if (j + 1 < p.size() && p[j + 1] == '*') {
            return backtrack(s, p, i, j + 2) || (firstMatch && backtrack(s, p, i + 1, j));
        } else {
            return firstMatch && backtrack(s, p, i + 1, j + 1);
        }
    }
};

❌ Not preferred due to exponential complexity.

---

Conclusion

✅ Best approach: Dynamic Programming (DP) with O(m * n) complexity.
✅ Avoids exponential backtracking while ensuring correct results.
✅ Uses only O(m * n) space, making it efficient for m, n ≤ 20.

Recommended Problems for Practice

1. Wildcard Matching 🎭
2. Valid Parentheses 🔢
3. Longest Common Subsequence 🧩

🚀 Master Regular Expressions with Efficient DP Solutions!