LeetCode 5 最长回文子串

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

方法1：暴力解法 也就是我第一时间想到的解法，结果，emmmm 超时了
思路就是遍历每一种组成字符串的可能，然后将每一次遍历到的字符串进行反转再比较看是否相等。
特殊情况的字符串总长度为0和为1时，直接返回该字符串即可
源代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int num[2000] = {0};
        int q = 0;
        string lastStr;
        string finalStr;
        if (s.length() == 0 || s.length() == 1) {
            return s;
        }
        for (int i = 0; i < s.length()-1; i++) {
            string str;
            str += s[i];
            for (int j = i+1; j < s.length(); j++) {
                str += s[j];
                //逆序
                string rStr(str.rbegin(), str.rend());
                if (str == rStr) {
                    num[q] = j - i + 1;
                }
            }
            if (num[q] != 0) {
                finalStr = s.substr(i, num[q]);
            }
            if (finalStr.length() > lastStr.length()) {
                lastStr = finalStr;
            }
            q++;
        }
        if (lastStr.length() == 0) {
            //substr 提取指定位置的str字符串
            return s.substr(0,1);
        }
        return lastStr;
    }
};

但上面这样做是超时的！ 虽然解法正确 所以就得用新的方法——动态规划
动态规划的思路比较巧妙
类似于中心扩散法，首先想想，作为回文串，他的首尾两个字符应该相等，那么再左右都向里压缩一个字符单位，那么如果压缩后剩余的字符单位数量大于1，则这两个字符单位也相等，然后继续左右压缩。如果压缩后剩余字符单位为1 那么该串必为回文串
所以动态规划的解题步骤：
1.定义一个二维数组bool dp[len-1][len-1]来记录遍历字符串所得的状态，dp[l][r]为true表示从l到r的子串为回文串，false表示不是回文串
2.初始化二维数组，单个字符为回文串，所以定义dp[i][i] = true
3.找到状态转移方程，dp[l][r] = (s[r]==s[l] && (r-l==1 || dp[l+1][r-1])) ? true : false

源代码如下:

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        if (len == 0)
            return s;
        bool dp[len][len];
        int start = 0, end = 0;
        for (int i = 0; i < len; i++)
            dp[i][i] = true;
        for (int r = 1; r < len; r++)
            for (int l = 0; l < r; l++)
                if (s[r]==s[l] && (r-l==1 || dp[l+1][r-1])) {
                    dp[l][r] = true;
                    if (r-l > end-start) {
                        start = l; end = r;
                    }
                    continue;
                }else
                    dp[l][r] = false;
        return s.substr(start, end-start+1);
    }
};