</>Ali · LeetCode
#0010·HardDynamic Programming

Regular Expression Matching

LeetCode #10 · Hard · Dynamic Programming · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Dynamic Programming (Top-Down with Memoization)

Key insight

The problem has optimal substructure and overlapping subproblems. We can use recursion with memoization to solve it efficiently.

Strategy

  1. 1Base Case: If we reach the end of the pattern (j == pattern.size()),
  2. 2Check if the first character of the current substring matches (text[i]
  3. 3Handle the '*' wildcard (peek at p[j+1]):
  4. 4Handle standard matching when no '*' follows: Match the character and
Time
O(S * P)
S and P are lengths of string and pattern.
Space
O(S * P)
the memoization table.
Problem description(from LeetCode)

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

Examples

Example 1
Input:
s = "aa", p = "a"
Output:
false

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.

C++ Solution

solution.cpp
class Solution {
public:
  vector<vector<int>> memo;
bool isMatch(string s, string p) {
    memo.assign(s.size() + 1, vector<int>(p.size() + 1, -1));
    if (p == "") return s == "";
    return dp(0, 0, s, p);
  }

  bool dp(int i, int j, const string &text, const string &pattern) {
    if (memo[i][j] != -1) return memo[i][j];

    bool result;
    if (j == pattern.size()) {
      result = (i == text.length());
    } else {
      bool firstMatch =
          (i < text.size() && (text[i] == pattern[j] || pattern[j] == '.'));

      if (j + 1 < pattern.size() && pattern[j + 1] == '*') {
        // Case 1: Match 0 of the preceding element (jump over pattern[j]*)
        // Case 2: Match 1 or more (only if firstMatch is true, move string
        // pointer)
        result = (dp(i, j + 2, text, pattern) ||
                  (firstMatch && dp(i + 1, j, text, pattern)));
      } else {
        // Normal character match
        result = (firstMatch && dp(i + 1, j + 1, text, pattern));
      }
    }

    return memo[i][j] = result;
  }
};

More Dynamic Programming problems