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?
Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers
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;
}
Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers