Loading...
Loading...
Loading...
Meera plays a word game with her hostel friends. She cuts a word into pieces so that every piece reads the same forwards and backwards, like level, noon or a single letter. Such a piece is called a palindrome.
Print every way to cut the word into palindrome pieces, keeping the letters in their order. Write each way as its pieces separated by spaces. Print the ways in dictionary order: compare the first pieces, then the second pieces, and so on. A piece that is the start of a longer piece comes first.
Example 1
Input
aab
Output
a a b aa b
a a b comes before aa b because the first piece a is the start of aa.
Example 2
Input
madam
Output
m a d a m m ada m madam
Single letters always work, and ada and madam are palindromes too.
Try the problem first. Open one hint at a time.
Choose the first piece, then cut the rest of the word in every possible way.
From position start, try every end. Keep the piece s.substring(start, end) only if it is a palindrome.
When start reaches the end of the word, the pieces in your list form one full answer.
Try shorter pieces first and the answers come out in the required order. Remove the piece after the recursive call.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor