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 .. 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. 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