You get a string s of lowercase letters. Return every way to cut s into pieces that are all palindromes.
A palindrome reads the same backwards, like "level". A single letter is a palindrome too.
The pieces keep the letters in their order. Each letter goes into exactly one piece. Write each way as a list of its pieces, from left to right.
List the ways by their first piece, shortest first. When two ways share a first piece, compare their second pieces the same way. Then the third, and so on.
That is the order you get when you always try the shortest next piece first.
Example 1:
Input: s = "noon" Output: [["n","o","o","n"],["n","oo","n"],["noon"]] Explanation: Every single letter is a palindrome. "oo" in the middle is a palindrome too. So is the whole word "noon". The two ways that start with "n" come first. Between them, "o" is shorter than "oo".
Example 2:
Input: s = "cat" Output: [["c","a","t"]] Explanation: "ca", "at" and "cat" are not palindromes. So each letter must be its own piece.
Example 3:
Input: s = "bbb" Output: [["b","b","b"],["b","bb"],["bb","b"],["bbb"]] Explanation: Any run of b's is a palindrome. The first pieces are "b", "b", "bb" and "bbb". Two ways start with "b". Their second pieces, "b" and "bb", put them in order.
Constraints:
shas 1 to 12 letters.- Each letter is a lowercase English letter, from a to z.
Your solution should run in O(n · 2ⁿ) time, where n is the length of s.
Hints:
Choose the first piece. It starts at the first letter and must be a palindrome. Then cut the rest of the string the same way.
Use backtracking. A helper gets start, the first letter not yet in a piece. It tries every end from start on. When the letters from start to end form a palindrome, it adds that piece. Then it calls itself from end + 1 and removes the piece again. When start reaches the end of
s, the pieces are one full way: save a copy.
Between two neighbouring letters you either cut or you don't. So there are at most 2ⁿ⁻¹ ways. Checking and copying one way takes O(n): O(n · 2ⁿ) time.
Besides the answer, the pieces being built and the open calls take O(n) extra space.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
