@roc571 no need to add memo to each recursive call. The dictionary is created when the function encode is created, and the default value of the memo argument is the reference/id/pointer/address to that dictionary.
@yaopiupiupiu Yeah, I think your are right. I think I forgot the inner loop, but substr won't make difference here, as the comparison takes also linear time. I believe it is actually O(Number_of_divisors * Length_of_string) which is bounded by O(n^1.5), which seems cumbersome.
What's more, so far, I can not see how to reduce this complexity but it seems to me that it's kind of huge. I would be glad to hear if there is any idea to improve it!
Nice solution, clear and neat code and runs very fast. I think the time complexity should be O(n^4), where n is the length of s. The outer loop plus find prefix contributes n^2, while the mem map will store up to all potential substrings of s, which contributes n^2, so the final time complexity should be O(n^4)
How did you get O(n^3)? Your for loop recursive function looks worse than n!. Just imagine a large n, you break that up in every partition and then do another recursive call for each part. (1,n-1),(2,n-2)...etc