The time complexity without memoezation is O(n^m) where n is the the size of the work bank and m is the length of the word. With memoezation it is O(n^2)
1 Like
Hello @Peter_Litvak,
We are using recursion in the solution so it always works with time complexity of O(n^2).
For example: If we have word abcd, it can be partitioned into abc and d only but if it was to be partitioned in any combination like abc/bac/cab then it would result in O(n^m).
Hmm, I don’t think it is correct, please take a look at the explanation of the problem here.
At about 2:28:30 time mark