How to convert a recursive solution to bottom up or top down solution?

Question

I am solving this problem-

Given a string consisting of a,b and c's, we can take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly?

Now I have written the following recursive solution (far from efficient), but want to convert it to either top-down or bottom-up solution.

Problem: I am not able to come up with a tabular structure for memoization. Even though I have to output only the length of resulting string, how can I solve it without actually solving the problem. The strings are getting reduced, so how do I store them?

Any hint for DP solution or Memoization would be great!

EDIT Many people have come up with top-down memoization solution, please try bottom-up as well.

#include <iostream>
#include <string>

using namespace std;

string reduce(string s)
{
    if (s.length() <= 1)
        return s;

    int k;
    char c = s[0];
    string min = s;
    for (k = 1; k < s.length() && c; ++k)
        if (s[k] != c)
            c = 0;
    if (c)
        return s;

    if (s.length() == 2){
        if (s[0] != 'a' && s[1] != 'a')
            s[0] = 'a';
        else if (s[0] != 'b' && s[1] != 'b')
            s[0] = 'b';
        else if (s[0] != 'c' && s[1] != 'c')
            s[0] = 'c';
        s.resize(1);
        return s;
    }

    for (k = 1; k < s.length(); ++k){
        string s1 = reduce(s.substr(0, k));
        string s2 = reduce(s.substr(k));

        if (s1.length() + s2.length() < min.length())
            min = s1 + s2;
        if (!s1.empty() && !s2.empty() && s1.back() != s2.front()){
            if (s1.back() != 'a' && s2.front() != 'a')
                s1.back() = 'a';
            else if (s1.back() != 'b' && s2.front() != 'b')
                s1.back() = 'b';
            else if (s1.back() != 'c' && s2.front() != 'c')
                s1.back() = 'c';
            s1 = reduce(s1 + s2.substr(1));
            if (s1.length() < min.length())
                min = s1;
        }

    }
    return min;
}

int main()
{
    string input;
    cin >> input;
    cout << reduce(input) << endl;
    return 0;
}

Answer 1

I'm a bit too lazy to think the problem through, but I'll give you an approach to memoization that often enough works.

Instead of recursing directly, introduce mutual recursion.

std::string reduce(std::string const &s)
{
    // ...
    string s1 = reduce_memo(s.substr(0, k));
    string s2 = reduce_memo(s.substr(k));
    // ...
}

where reduce_memo maintains a hash table, i.e. an unordered_map, mapping subproblems to their solutions.

// static is incredibly ugly, but I'll use it here for simplicity
static std::unordered_map<std::string, std::string> memo;

std::string reduce_memo(std::string const &s)
{
    try {
        return memo.at(s);
    } except (std::out_of_range const &) {
        std::string r = reduce(s);
        memo[s] = r;
        return r;
    }
}

When programming in C++98, use std::map instead of unordered_map.

Answer 2

This doesn't solve the problem, but I noticed:

if (s.length() == 2){
    if (s[0] != 'a' && s[1] != 'a')
        s[0] = 'a';
    else if (s[0] != 'b' && s[1] != 'b')
        s[0] = 'b';
    else if (s[0] != 'c' && s[1] != 'c')
        s[0] = 'c';
    s.resize(1);
    return s;
}

doesn't work according to the problem statement:

we can take any two adjacent distinct characters and replace it with the third character.

Consider the string s = "bb". Neither s[0] nor s[1] are equal to 'a', which means the condition s[0] != 'a' && s[1] != 'a' will evaluate to true for the string "bb". This goes for any string of consecutive characters of the same value, e.g. "bb", "cc".

Perhaps in the condition you can take the difference of the two consecutive characters, and check if they're non-zero.

Answer 3

You can memoize your solution by storing the result of reduce(s) in a map<string,string>.

string reduce(string s, map<string,string>& memo) {
    if (memo.count(s)) {
        return memo[s];
    }
    // The rest of your code follows...
    memo[s] = min;
}