Cut a string into palindromes
A palindrome is a string that reads the same forwards and backwards, such as "level", "oo" or any single letter. You get a string s. Return every way to cut s into pieces of one or more letters so that every piece is a palindrome.
Write each way as a list of its pieces from left to right, so that joining the list gives back s. Return each way once, in any order. There is always at least one way: cutting s into single letters.
s = "noon"Output[["n", "o", "o", "n"], ["n", "oo", "n"], ["noon"]]Single letters always work. "oo" is a palindrome, and so is the whole word. A piece such as "no" is not.
s = "abc"Output[["a", "b", "c"]]"ab", "bc" and "abc" are not palindromes, so single letters are the only way.
s = "aaa"Output[["a", "a", "a"], ["a", "aa"], ["aa", "a"], ["aaa"]]Every piece of "aaa" is a palindrome. Each of the 2 gaps between letters is cut or not, so all 4 ways count.
1 ≤ len(s) ≤ 24
sholds only lowercase English letters.There are at most 5,000 ways to cut
sinto palindromes.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.