Friday, September 6, 2013

Palindrome String II@leetcode

刷题必备书籍Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历: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
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 = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
» Solve this problem

刚开始还是用的回溯,和I一样,这样可以做,但是会超时在跑大数据的时候。然后参考了“水中的鱼”的博客,用的DP。并且他总结,一般求最优的时候,都是用dp,不过要自己设计dp函数和情况,这道题靠裸想还是有些难度的,如果对dp不熟悉的话。

首先要定义一个函数D[i]=min(D[i], D[j+1]+1). 假如此时 P[i][j]是一个palindrome。记得要初始化,相当于就有两个指针,i, j,i从s.size()处开始,j从i开始往s.size()处数,这样最后D[0]-1的值就是最小的cut 数。

所以这个时候我们还要定义一个P[i][j]=true if S[i]==S[j]&&(j-i<2 || P[i+1][j-1]) 

记得初始化!


No comments:

Post a Comment

Leetcode 316. Remove Duplicate Letters

 这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...