Cutting a Word Into Palindromes

Medium

You get a word word. Cut it into contiguous pieces so that every piece is a palindrome, meaning it reads the same forwards and backwards. A single letter counts as a palindrome. Return every possible way to cut it. Each way is a list of pieces in the order they appear in the word. The ways themselves may be listed in any order.

Example 1

word="noon" → [['n', 'o', 'o', 'n'], ['n', 'oo', 'n'], ['noon']]

You can cut it into single letters, keep the middle "oo" together, or leave the word whole, since it is a palindrome itself.

Example 2

word="xyx" → [['x', 'y', 'x'], ['xyx']]

"xy" and "yx" are not palindromes, so there are only two ways.

Example 3

word="q" → [['q']]

Constraints

1 ≤ len(word) ≤ 16
word consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming Backtracking

Similar problems

All Balanced Bracket Strings Medium Two Disjoint Palindromic Picks Medium Binary String Made of Powers of Five Medium Every Way to Space the Words Hard Best Word Set From Tiles Hard

Input

word="noon"

Expected

[['n', 'o', 'o', 'n'], ['n', 'oo', 'n'], ['noon']]

Run checks the first 3 tests in your browser. Submit checks all 112 tests on the server, hidden ones included.