search

xqian / cpp_projects

cplusplus projects for myself
2 stars 2 forks source link

Palindrome Partitioning II (find minimum dividen count) #8

Closed xqian closed 11 years ago

xqian commented 11 years ago

http://leetcode.com/onlinejudge#question_132

xqian commented 11 years ago

small case test passed. When the string is very long, matrix is faster than map.

But the large cases, is still failing, anyway to make it faster?

Run Status: Accepted! Program Runtime: 12 milli secs

Progress: 12/12 test cases passed. input output expected
"a" 0 0

"ab" 1 1

"bb" 0 0

"cdd" 1 1

"dde" 1 1

"efe" 0 0

"fff" 0 0

"abbab" 1 1

"leet" 2 2

"coder" 4 4

"abcccb" 1 1

"cabababcbc" 3 3

xqian commented 11 years ago

still not passed leetcode yet. so leave it open

tj2013 commented 11 years ago

Comment:

1) use a matrix, check each element. I think that may not be necessary because the matrix is sparse. So I use vector of vector 2) the complexity of your program is O(N^3), I think isPalindrom is called O(N^2) times, and the function costs O(N)

On Fri, May 31, 2013 at 1:09 AM, Xin Qian notifications@github.com wrote:

still not passed leetcode yet. so leave it open

— Reply to this email directly or view it on GitHubhttps://github.com/xqian/cpp_projects/issues/8#issuecomment-18730319 .

xqian commented 11 years ago

2) the complexity of your program is O(N^3), I think isPalindrom is called

O(N^2) times, and the function costs O(N)

I think you are right.

On Fri, May 31, 2013 at 11:34 AM, tj2013 notifications@github.com wrote:

Comment:

1) use a matrix, check each element. I think that may not be necessary because the matrix is sparse. So I use vector of vector 2) the complexity of your program is O(N^3), I think isPalindrom is called O(N^2) times, and the function costs O(N)

On Fri, May 31, 2013 at 1:09 AM, Xin Qian notifications@github.com wrote:

still not passed leetcode yet. so leave it open

— Reply to this email directly or view it on GitHub< https://github.com/xqian/cpp_projects/issues/8#issuecomment-18730319> .

— Reply to this email directly or view it on GitHubhttps://github.com/xqian/cpp_projects/issues/8#issuecomment-18763326 .

QIAN, Xin (xqian@unh.edu chianshin@gmail.com) http://www.sciencenet.cn/u/chianshin/

xqian commented 11 years ago

This is also the point that I can improve.

isPalindrom for the whole string definitely can be improve to N^2

On Fri, May 31, 2013 at 12:51 PM, Xin Qian chianshin@gmail.com wrote:

2) the complexity of your program is O(N^3), I think isPalindrom is called

O(N^2) times, and the function costs O(N)

I think you are right.

On Fri, May 31, 2013 at 11:34 AM, tj2013 notifications@github.com wrote:

Comment:

1) use a matrix, check each element. I think that may not be necessary because the matrix is sparse. So I use vector of vector 2) the complexity of your program is O(N^3), I think isPalindrom is called O(N^2) times, and the function costs O(N)

On Fri, May 31, 2013 at 1:09 AM, Xin Qian notifications@github.com wrote:

still not passed leetcode yet. so leave it open

— Reply to this email directly or view it on GitHub< https://github.com/xqian/cpp_projects/issues/8#issuecomment-18730319> .

— Reply to this email directly or view it on GitHubhttps://github.com/xqian/cpp_projects/issues/8#issuecomment-18763326 .

QIAN, Xin (xqian@unh.edu chianshin@gmail.com) http://www.sciencenet.cn/u/chianshin/

QIAN, Xin (xqian@unh.edu chianshin@gmail.com) http://www.sciencenet.cn/u/chianshin/

xqian commented 11 years ago

http://discuss.leetcode.com/questions/1266/palindrome-partitioning-ii http://www.cppblog.com/wicbnu/archive/2013/03/18/198565.html

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.

题解： 类似矩阵连乘的动归思路。 dp[i][j]=min(dp[i][k]+dp[k+1][j]+1), i<=k<j. 但是用这个方程的时间是O(n^3)，简化dp[i][j]为dp[i]，表示从0到i的minCut. dp[i]=min(dp[k]+1(s[k+1, i]是回文串, dp[k]+i-k(s[k+1, i]不是回文串)), 0<=k<i.

xqian commented 11 years ago

tengjing's solution3 is good on:

//palLens[start_point][length of palindrome]
//numSeg[start_point], numSeg of [start_point,end_of_string]
//cur from 0 until increase to cur + palLens[cur][i]
//smarter on using the known palindrome to step forward