leetcode 第五题: Longest Palindromic Substring

求最长回文子串的问题。是一个很经典的题目。我这里通过在n^2的算法基础上做了优化过的。源码如下

https://github.com/unasm/utils/blob/master/palindromic.c

首先,如kmp算法一般,首先对字符串进行扫描,在pos中记录每一个相同字符的前一个字符位置,第一个为-1,


for (len = 0; s[len] != '\0'; len++) {
pos[len] = hash[s[len]];
hash[s[len]] = len;
}

这里将pos中保存前一个字符的位置,方便快速跳过无用的字符。

这里利用了一个回文字符串的性质,就是如果abba是回文字符串,那下标 a+a = b+b的下标,所以根据dp的思想,判断两个字符是不是可以构成回文字符串,需要判断两个条件就是了,第一,这两个字符相同,第二个,题目之间包裹的字符串构成回文字符串,而判断中间构成回文字符串的语句就是

1 . if(i – last <= 2)  如果两个相同字符之间只有一个或者没有字符,则中间是回文子串,如果大于1个,则 i –  hash[i + last] = 1,也就是说,两个字符的中心必须有过回文字符串,并且,上一个构成回文字符串的位置必须和现在的字符挨着,hash[i+last]中记录着上一个以i+last为中心的回文串的大值所处的位置,如果添加两个之后依旧构成回文串,则他们必须挨着,

最后可以根据 当前的最大位置和两者相加的结果判断出来回文串的长度。

从以上可以看出来,其实就是在o(n^2)的基础上,加了一个快读跳过的设置而已

Leave a comment

Your email address will not be published.

*