solved 'Regular Expression Matching' on LeetCode https://leetcode.com/problems/regular-expression-matching/

regex.cc

#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

bool isMatch(string s, string p) {
  int s_len = s.size(), p_len = p.size();
  vector<vector<bool>> matched(p_len + 1, vector<bool>(s_len + 1, false));

  matched[0][0] = true;
  for (int i = 1; i <= p_len; ++i) {
    // Match sub string until i-th of p.
    if (p[i - 1] != '*') {
      for (int j = 1; j <= s_len; ++j) {
        matched[i][j] =
            matched[i - 1][j - 1] && (p[i - 1] == '.' || p[i - 1] == s[j - 1]);
      }
    } else {
      // Init the first matching record in case the second char of p is '*'.
      if (i == 2) {
        matched[i][0] = true;
      } else {
        matched[i][0] = matched[i - 2][0];
      }
      // Wildcard matching begins.
      for (int j = 1; j <= s_len; ++j) {
        matched[i][j] =
            matched[i - 2][j] ||
            (matched[i][j - 1] && (p[i - 2] == s[j - 1] || p[i - 2] == '.'));
      }
    }
  }
  return matched[p_len][s_len];
}

int main() {
  // Simple test cases.
  assert(isMatch("aa", "aa"));
  assert(isMatch("aa", "a*"));
  assert(isMatch("aa", ".*"));
  assert(isMatch("aa", "ab*a"));
  assert(!isMatch("aa", "ab"));
  assert(isMatch("aa", "c*a*b*"));
  assert(!isMatch("ab", ".*c"));
}