educative.io

Educative

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?


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