Why memoize solution #2?

There don’t appear to be any recursive calls to dp with the repeat cached indices, so when would the cached results ever be used?

Yeah confirmed, the memoization construct is unused in solution #2.

Here’s the code - I added some logging to the conditional block which executes when a memoized result is used, but no output for any of the test cases.

#include <iostream>

#include <string>

#include <unordered_map>

using namespace std;

// Top down memoization

// Memoization -> cache intermediate

unordered_map<string, bool> cache;

// marker i for text string and marker j for pattern string

bool dp(const string& text, const string& pattern, int i, int j) {

string ij_pair = "(" + to_string(i) + ", " + to_string(j) + ")";

if (cache.find(ij_pair) != cache.end()) {

cout << "Using cached result for " << ij_pair << '\n';

return cache[ij_pair];

}

// Base case 1

// If i is out of bounds and j is out of bounds, then we have found our answer

if (i >= text.length() && j >= pattern.length()) {

return true;

}

// Base case 2

// If i is not out of bounds but j is out of bound then return false,

// there are some characters in text string that we haven't matched.

if (j >= pattern.length()) {

return false;

}

// The bool value of match will be True if there is a match otherwise it will

// be False

bool match =

(i < text.length() &&   // For match, the ith index must be less than the

// length of the text string

(text[i] == pattern[j] ||   // match between text[i] and pattern[j]

pattern[j] == '.'));        // current pattern character is the "."

// wildcard, so any character in the text

// is acceptable

// If the character present on index (j+1) in pattern string is a "*"

if ((j + 1) < pattern.length() && pattern[j + 1] == '*') {

// If either of them evaluates to True then we return true

// Skipping "*" and recursively calling the dp function with the advanced

// indices

bool bool1 = dp(text, pattern, i, j + 2);

// use *, remember that we can only use the "*" if there is a match

bool bool2 = (match && dp(text, pattern, i + 1, j));

bool new_bool = bool1 || bool2;

cache[ij_pair] = new_bool;

return cache[ij_pair];

}

// If we do not have a "*" character, then we are only looking for a match

if (match) {

cache[ij_pair] = dp(text, pattern, i + 1, j + 1);

return cache[ij_pair];

}

// If there is neither a "*" nor a match, then we simply store False in cache

if (cache.find(ij_pair) != cache.end()) {

cache[ij_pair] = false;

}

return false;

}

bool RegxMatch(const string& text, const string& pattern) {

cache.clear();

return dp(text, pattern, 0, 0);

}

int main() {

cout << boolalpha;

cout << "RegxMatch(\"aa\", \"a\"): " << RegxMatch("aa", "a") << endl;

cout << "RegxMatch(\"aa\", \"a*\"): " << RegxMatch("aa", "a*") << endl;

cout << "RegxMatch(\"ab\", \".*\"): " << RegxMatch("ab", ".*") << endl;

cout << "RegxMatch(\"aab\", \"c*a*b\"): " << RegxMatch("aab", "c*a*b") << endl;

cout << "RegxMatch(\"mississippi\", \"mis*is*p*.\"): " << RegxMatch("mississippi", "mis*is*p*.") << endl;

}