Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Palindromic Partitioning

Problem Statement

Given a string, we want to cut it into pieces such that each piece is a palindrome. Write a function to return the minimum number of cuts needed.

Example 1:

Input: "abdbca"
Output: 3
Explanation: Palindrome pieces are "a", "bdb", "c", "a".

Example 2:

Input: = "cddpd"
Output: 2
Explanation: Palindrome pieces are "c", "d", "dpd".

Example 3:

Input: = "pqr"
Output: 2
Explanation: Palindrome pieces are "p", "q", "r".

Example 4:

Input: = "pp"
Output: 0
Explanation: We do not need to cut, as "pp" is a palindrome.

.....

.....

.....

Like the course? Get enrolled and start learning!
K

Keerthana Koorapati

· 5 years ago

Finding it hard to understand the bottom up approach for palindromic partitioning.

Did anyone find any useful links or videos reg it?

Show 1 reply
R

Ray

· 4 years ago

In the JS top down recursive DP with Memo, the memo (dp) is not used to memoize the values in findMPPCutsRecursive(). Only the string palindromes are memoized in dpIsPalindrome.

G

Gary

· 4 years ago

For brute force approach, why do we cut when there is a palindrome in the for loop?

At top of the recursive function, we do NOT cut if it's a palindrome, so I'm confused by the different treatment here.

Show 2 replies