solved 'Wildcard Matching' on LeetCode https://leetcode.com/problems/wildcard-matching/

wildcard_dp.cc

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

using namespace std;

// DP, O(mn). Runtime: 1304 ms.
class Solution {
 public:
  bool isMatch(string s, string p) {
    int s_len = s.size(), p_len = p.size();
    // DP data for each char in s with fixed char in p.
    vector<bool> matched_records(s_len + 1, false);
    // Empty p matched empty s (before s[0]).
    matched_records[0] = true;

    for (char p_ch : p) {
      if (p_ch != '*') {
        // Reverse iteration to use previous results -
        // Match iff previous position of p matches and current char in both
        // strings match.
        for (int s_i = s_len; s_i >= 1; --s_i) {
          matched_records[s_i] = matched_records[s_i - 1]
              && (p_ch == '?' || s[s_i - 1] == p_ch);
        }
      } else {
        // Wildcard. Match if any previous char of s has been matched.
        for (int s_i = 1; s_i <= s_len; ++s_i) {
          matched_records[s_i] =
              matched_records[s_i] || matched_records[s_i - 1];
        }
      }
      // Update the first record. Match iff all previous chars of p are '*'.
      matched_records[0] = matched_records[0] && (p_ch == '*');
    }
    return matched_records.back();
  }
};

int main(int argc, char *argv[]) {
  Solution sol;

  assert(sol.isMatch("aa", "a") == false);
  assert(sol.isMatch("aa", "aa") == true);
  assert(sol.isMatch("aaa", "aa") == false);
  assert(sol.isMatch("aa", "a?") == true);
  assert(sol.isMatch("aa", "*") == true);
  assert(sol.isMatch("aa", "a*") == true);
  assert(sol.isMatch("aa", "?*") == true);
  assert(sol.isMatch("aab", "c*a*b") == false);
  assert(sol.isMatch("cab", "c*b") == true);
  assert(sol.isMatch("cafasdfb", "c*b") == true);
  assert(sol.isMatch("0afasdf1vczxcve2", "0*1*2") == true);
}

wildcard_pointers.cc

#include <cassert>
#include <iostream>

using namespace std;

// Algorithm from
// https://leetcode.com/discuss/10133/linear-runtime-and-constant-space-solution
// May be linear runtime (but pointers can go backward so may not) and constant
// space solution. Runtime: 16 ms
class Solution {
 public:
  bool isMatch(string s, string p) {
    int s_len = s.size(), p_len = p.size(), s_idx = 0, p_idx = 0;
    int s_wild_match_begin = 0, p_star_pos = -1;
    while (s_idx < s_len) {
      if (p_idx < p_len && (p[p_idx] == '?' || s[s_idx] == p[p_idx])) {
        ++p_idx, ++s_idx;
      } else if (p_idx < p_len && p[p_idx] == '*') {
        p_star_pos = p_idx;
        ++p_idx;
        s_wild_match_begin = s_idx;
      } else if (p_star_pos != -1){
        // Failed matching wildcard. Revert to beginning of wildcard.
        p_idx = p_star_pos + 1;
        // Move forward the recorded pointer in s.
        ++s_wild_match_begin;
        s_idx = s_wild_match_begin;
      } else {
        return false;
      }
    }
    // `p` may have remaining parts. Failed to match if any of them is not '*'.
    for (; p_idx < p_len; ++p_idx) {
      if (p[p_idx] != '*') {
        return false;
      }
    }
    return true;
  }
};


int main(int argc, char *argv[]) {
  Solution sol;

  assert(sol.isMatch("aa", "a") == false);
  assert(sol.isMatch("aa", "aa") == true);
  assert(sol.isMatch("aaa", "aa") == false);
  assert(sol.isMatch("aa", "a?") == true);
  assert(sol.isMatch("aa", "*") == true);
  assert(sol.isMatch("aa", "a*") == true);
  assert(sol.isMatch("aa", "?*") == true);
  assert(sol.isMatch("aab", "c*a*b") == false);
  assert(sol.isMatch("cab", "c*b") == true);
  assert(sol.isMatch("cafasdfb", "c*b") == true);
  assert(sol.isMatch("0afasdf1vczxcve2", "0*1*2") == true);
}