[Leetcode Solution] Palindrome Partitioning 2

WRONG ANSWER MANY TIMES

Analysis

• Straightforward idea by dynamic programming
• f[i] denotes the min cuts for the sub-string from 0 to i
• If sub string(0..i) is a palindrome, f[i]=0
• Else f[i]=min(f[j-1]+1) in which sub string(j..i) is a palindrome

Note

• At first I do palindrome check for each string if needed. Exceed time limits
• At the palindrome check function, use a hash table to store the calculated result. Maybe recursive function still takes time, exceed time limits as well
• Compute the palindrome check for all the sub string combinations iterative, pass the tests
• If the common sub problem is calculated many times, the results should be stored rather then calculate each time when needed.
• Attention must be paid if the length and index and used simultaneously because the value is very likely to be mistake by one more or one less  

Code

UPDATED AT 3RD PASS