leetcode_5

发表于   |   分类于

Longest Palindromic Substring

题目戳这

题意

求最长回文子串

解法

求最长回文子串是很经典的问题啊，有很多种解法，最基本的就是用暴力，时间复杂度是log(n^3),再者就是用经典的dp解法，时间复杂度为log(n^2),更进阶的使用manacher算法，时间复杂度为log(n)，就这道题目来说，最长的串为1000,那么用n^2的复杂度就可以。

我们用table[i][j]来记录字符串从i到j是否为回文串，很显然，table[i][i]=1,然后同时我们也可以初始化table[i][i+1]，只要比较s[i]和s[i+1]是否相等即可。
最关键的状态转移方程就是如果s[i]==s[j]并且table[i+1][j-1]，则table[i][j]=table[i+1][j-1]，这是很显然的。

我刚开始用python时老是超时，后来换用C++可以过。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if(len == 0){
            return "";
        }
        int flag[1010][1010];
        memset(flag, 0, sizeof flag);
        int mmax = 1;
        string res = s.substr(0, 1);
        int start = 0;
        for(int i=0;i<len;i++){
            flag[i][i] = 1;
            if(i+1<len && s[i] == s[i+1]){
                start = i;
                mmax = 2;
                flag[i][i+1] = 1;
            }
        }
        for(int slen = 3;slen < len+1; slen++){ //枚举回文串长度，注意有可能长度为len
            for(int i = 0;i+slen-1 < len; i++){
                int j = i + slen - 1; //此时j的值          
                if(flag[i+1][j-1] && s[i] == s[j]){
                    flag[i][j] = flag[i+1][j-1];
                    mmax = slen;
                    start = i;
                }
            }
        }
        if(mmax>=2)
            return s.substr(start, mmax);
        return res;
    }
};