Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Subscribe to see which companies asked this question

Show Tags

Show Similar Problems

 这里用的是DP，搜了一下，是有更好的办法，以后再了解吧

class Solution {
public:
    /*
     *  使用DP.DP考虑2点,状态和状态转化矩阵
     *
     * 状态为 f[i][i] = 1,
     * f[i][i+1]=1 ,当 s[i] == s[i + 1]
     * 状态转移矩阵为 f[i][j] = f[i+1][j-1] ,当 s[i] == s[j]
     */
    string longestPalindrome(string s) {
        int f[1000][1000];
        int i;
        int j;
        int max_len = 1;
        int start_index = 0;
        int len_s = s.length();

        for (i=0; i<len_s; i++)
            for(j=0; j<len_s; j++)
                f[i][j] = 0;

        for (i=0; i<len_s; i++) {
            f[i][i] = 1;
        }
        for (i=0; i<len_s-1; i++) {
            if (s[i] == s[i+1]) {
                f[i][i+1] = 1;
                max_len = 2;
                start_index = i;
            }
        }

        //上面考虑完长度为2的子串的情况,下面考虑长度大于2的子串
        for (i=3; i<=len_s; i++) {
            for (j=0; j<=len_s-i; j++) {
                int k =  i + j - 1;
                if (s[j] == s[k]) {
                    if (f[j+1][k-1]) {
                        f[j][k] = 1;
                        if (max_len < i) {
                            max_len = i;
                            start_index = j;

                        }
                    }
                }
            }
        }
        return s.substr(start_index, max_len);
    }
};