CodeWAR , my solution gives TLE ..please help !!

general
, , ,
1

I tried using recursion and memoization.

problem link link text

here is my solution

#include<bits/stdc++.h>
using namespace std;

string p,q;

map <string,int> memo;

string rev(string x){
string y="";
    for(int i=x.length()-1;i>=0;i--){
        y+=x[i];
    }
    return y;
}

bool solve(string p){
    if(p==q) return true;
    if(p.length()>=q.length() || p.length()>51) return false;

    if(memo[p]!=0) return memo[p]==2;

    bool ans = solve(p+"A")+solve("B"+rev(p));

    if(ans) return memo[p]=2;
    else return memo[p]=1;
}
I looked at the accepted solution they also used recursion and they tried to match the target string into the source while i tried to convert the source into the target string. I wonder how does it make a difference. please help!!
2

If you start with the target, you can only get substrings of the target (maybe reversed) during the algorithms. The number of those is bounded by O(n^2).

Starting with the source, you can produce far more intermediate strings. So your solution is TLE.

1 Like