Longest Palindromic Substring Part

reference:

http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html

http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html

http://www.felix021.com/blog/read.php?2040

Method 1:暴力算法。找出所有可能起始点(C(2,n)种可能),分别判断是不是回文(n)。最后复杂度是O(n^3).

Method 2: Method 1 + DP。例如:有ababa,如果已知bab是回文。在判断ababa时可省时间。

–Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.

— if P[i+1,j-1] true and Si=Sj —> P[i,j] true.       If P[i,i+1] true —>Si=Si+1          P[i,i] always true.

–我们先算一个字的回文,在此基础上再算两个字的回文,再算3个字的回文…算法的复杂度是O(n^2). 需要空间O(n^2)。

Method 3: 遍历每一个char。以每一个char为回文中心检查两边是否对称。时间复杂度O(n^2)。空间复杂度O(1)。

Method 4: 一个神奇的算法时间复杂度是O(n)http://www.felix021.com/blog/read.php?2040

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s