Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: 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!
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