题目

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.

分析

求给定字符串的最长回文子串。

这道题有下面三种解决思路：

1. 暴力法，二层遍历，判断【i，j】子串是否回文，且同时记录最长长度； 显然的，暴力解决必然TLE；

2. 字符串s中的最长回文串便是s的倒转_s与s的最长公共子串。题目转换为求最长公共子串；

3. 动态规划解决，类似于lcs的解法，数组flag[i][j]记录s从i到j是不是回文，参考网址；
   
   3.1. 首先初始化，i>=j时，flag[i][j]=true，这是因为s[i][i]是单字符的回文，当i>j时，为true，是因为有可能出现flag[2][1]这种情况，比如bcaa，当计算s从2到3的时候，s[2]==s[3]，这时就要计算s[2+1] ?= s[3-1]，总的来说，当i>j时置为true，就是为了考虑j=i+1这种情况。
   
   3.2. 接着比较s[i] ?= s[j]，如果成立，那么flag[i][j] = flag[i+1][j-1]，否则直接flag[i][j]=false；

AC代码

class Solution {

public:

    string longestPalindrome(string s) {

        int len = s.length(), max = 1, ss = 0, tt = 0;

        bool flag[len][len];

        for (int i = 0; i < len; i++)

            for (int j = 0; j < len; j++)

                if (i >= j)

                    flag[i][j] = true;

                else flag[i][j] = false;

        for (int j = 1; j < len; j++)

            for (int i = 0; i < j; i++)

            {

                if (s[i] == s[j])

                {

                    flag[i][j] = flag[i+1][j-1];

                    if (flag[i][j] == true && j - i + 1 > max)

                    {

                        max = j - i + 1;

                        ss = i;

                        tt = j;

                    }

                }

                else flag[i][j] = false;

            }

        return s.substr(ss, max);

    }

};

其它解法

class Solution {

public:

    /*方法一：暴力法*/

    string longestPalindrome1(string s) {

        if (s.empty())

            return false;

        //如果源串本身便是回文，则返回源串

        if (isPalindrome(s))

            return s;

        int len = s.length(), maxLen = 0;

        string ret = "";

        for (int i = 0; i < len; ++i)

        {

            for (int j = i + 1; j < len; ++j)

            {

                string str = s.substr(i, j - i);

                if (isPalindrome(str) && (j - i) > maxLen)

                {

                    ret = str;

                    maxLen = j - i;

                }//if

                else

                    continue;

            }//for

        }//for

        return ret;

    }

    /*方法二：字符串s中的最长回文串便是s的倒转_s与s的最长公共子串*/

    string longestPalindrome2(string s) {

        if (s.empty())

            return false;

        //如果源串本身便是回文，则返回源串

        if (isPalindrome(s))

            return s;

        //求字符串s的倒置

        string rs = s;

        reverse(rs.begin(), rs.end());

        return lcs(s, rs);

    }

    /*方法三：动态规划*/

    string longestPalindrome(string s)

    {

        if (s.empty())

            return false;

        int len = s.length(), maxLen = 1, from = 0, to = 0;

        vector<vector<int>> flag(len, vector<int>(len,0));

        for (int i = 0; i < len; ++i)

        {

            for (int j = 0; j < len; ++j)

            {

                //值为1表示 i,j 范围子串为回文串，i>j时值为1，针对j==i+1的情况

                if (i >= j)

                    flag[i][j] = 1;

            }//for

        }//for

        for (int j = 1; j < len; ++j)

        {

            for (int i = 0; i < j; ++i)

            {

                /*判断从i到j的子串是否为回文串，若字符相等*/

                if (s[i] == s[j])

                {

                    /*则i到j是否为子串由 i+1 到 j-1 决定*/

                    flag[i][j] = flag[i + 1][j - 1];

                    /*更新最长子串长度和起始结束位置*/

                    if (flag[i][j] == 1 && (j - i + 1) > maxLen)

                    {

                        maxLen = j - i + 1;

                        from = i;

                        to = j;

                    }//if

                }else

                    flag[i][j] = 0;

            }//for

        }//for

        return s.substr(from, maxLen);

    }

    /*求s和rs的最长公共子串*/

    string lcs(string s, string rs)

    {

        return "";

    }

    /*判断字符串s是否为回文串*/

    bool isPalindrome(string s)

    {

        if (s.empty())

            return false;

        int lhs = 0, rhs = s.size() - 1;

        while (lhs < rhs)

        {

            if (s[lhs] != s[rhs])

                return false;

            ++lhs;

            --rhs;

        }//while

        return true;

    }

};