Write palindrome_cuts(s: str) -> list[list[str]] that returns every way to cut s into consecutive pieces such that each piece reads the same forwards and backwards. Each way is the list of its pieces from left to right, so joining them gives back s.
- Every single letter is such a piece, so there is always at least one way.
- The ways can come back in any order, but the pieces inside each way must be in left-to-right order. Each way must appear once.
palindrome_cuts("noon") # [["n", "o", "o", "n"], ["n", "oo", "n"], ["noon"]] in some order
palindrome_cuts("aab") # [["a", "a", "b"], ["aa", "b"]]
palindrome_cuts("x") # [["x"]]
Constraints: 1 <= len(s) <= 16, lowercase letters only.
A string of n letters can have up to 2^(n-1) valid ways (try "aaaa"), so the output alone can be that big. Aim for O(n · 2^n) overall, and don't carry on cutting after a piece that doesn't read the same both ways.
Show hint
decide the first piece: try every prefix that reads the same both ways, then solve the rest of the string the same way and put that piece in front. Checking "same both ways" for every s[i..j] in advance makes each test O(1).