Palindrome Partitioning

Medium · Backtracking

You are given a string made of lowercase letters. Split it into consecutive pieces so that every piece, read on its own, is a palindrome. Return every way to do this, where each way is listed as the ordered sequence of pieces that reconstructs the original string. The order of the different splits in your result does not matter.

Examples

Input:  s = "aab"
Output: [["a","a","b"],["aa","b"]]
Why:    Both groupings split the string into pieces that each read the same forwards and backwards.

Input:  s = "a"
Output: [["a"]]
Why:    A single letter is trivially a palindrome, so the only split is the whole string as one piece.

Input:  s = "ab"
Output: [["a","b"]]
Why:    "ab" itself is not a palindrome, so the only valid split is into two single letters.

Constraints

1 <= s.length <= 16, s consists only of lowercase English letters

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Palindrome Partitioning

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Palindrome Partitioning. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.