简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
Question:
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s =
Return
"aab",Return
1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.Analysis:
The basic and straight forward solution of this problem is, find the palindrome of the string from the very start, once find one, get the minimum cut number of the rest string recursively. Use a vector to store the cut number and define a helper function to decide palindrome or not.
In this way, time limit exceed in huge test cases.
There are 2 parts that cost too much time.
1. Used a helper function to decide palindrome every time.
2. Recursively call of function.
The normal improvement methods for these two aspects are
1. Define a vector to memorize the palindrome judging results and make use of them which saves time in repeating judging.
2. Use a iterative way to search through the whole solution space instead of recursion.
We use DP here to solve the problem. DP works for many problem which asks for finding the optimal solution.
To define the equation and relationship for the problem first.
For example, we have a string
a a a a a a a a b b b a b b b
i j
D[i] equals the minimum cut number for string [i,n].
Thus, D[i] = min(D[i], D[j+1]+1) j<=i, and [j+1, i] forms a palindrome.
Then how to decide whether a string is a palindrome with dp?
We define P[i][j] = true if [i,j] is a palindrome
P[i][j] = str[i]==str[j]&&(j-i<2||p[i+1][j-1])
p[i+1][j-1] means the center part of string forms a palindrome.
a b b b a
i i+1 j-1 j
With these two DPs, we can solve this problem with optimal time cost.
The logic shown in your code is sort of different from your analysis? "Thus, D[i] = min(D[i], D[j+1]+1) j<=i, and [j+1, i] forms a palindrome." in above sentence, it should be "j >= i" instead of "j <= i" and [i, j] forms a palindrome, right?
ReplyDelete