I think worst case complexity is O(n^3).

multi = [self.encode(s[:i]) + self.encode(s[i:]) for i in xrange(1, n)]

This line basically runs over every substring of s. There are total of O(n^2) substrings, so this loop runs for O(n^2).

i = (s + s).find(s, 1)

Is O(n) which in worst case happens for every substring of s (O(n^2))

Memoization prevents exponential run time, some substrings may repeat but memo will quickly end the recursion

So all in all O(n^3) complexity....correct me if wrong.