given any string, generate splits into palindromes

https://leetcode.com/problems/palindrome-partitioning/

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

====analysis

I found this question quite hard and had no confidence, .. overwhelmed, like manyDP problems. But then I came up with two DP solutions .. https://github.com/tiger40490/repo1/blob/py1/py/algo_str/genPalindromSplits.py

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. It can mean two very important entities in the problem domain — either a palindrome substring or a complete family of substrings that form the original word. It’s crucial to avoid this word

insight — challenge is not O() but a working 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

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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