given any string, generate splits into palindromes

Q: Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.


I found this question quite hard and had no confidence, .. overwhelmed, like many DP problems. But then I came up with two DP solutions ..

I don’t bother to run the leetcode tests as they tend to deflate my burning joy, absorbency… precious stuff.

insight — the word “partition” is horribly confusing. A “partition” can mean two very important entities in this problem domain — either 1) a palindrome substring or 2) a complete family of substrings that form the original word. It’s crucial to avoid this word

insight — challenge is not O() but a correct solution that generates all splits without repetition

–idea 1: recursive top-down DP

memoization is not easy since I used generator.

–idea 2: iterative bottom-up DP

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s