第五题

解法一：

class Solution {
public:
    string longestPalindrome(string s) {
        int max_len = 0;
        string res = "";
        int ls = s.size();
        int i, j, k;
        for(i = 0; i < ls; i++){
            findpal(s,i-1,i+1,max_len,res);
        }
        for(i = 0; i < ls; i++){
            findpal(s, i, i + 1, max_len, res);
        }
        return res;
    }
    
private:
    void findpal(string s, int j, int k, int &max_len, string &res){
        while(j >= 0 && k <= s.size()-1 && s[j] == s[k]){
            j--;
            k++;
        }
        if(max_len < k - j -1){
            max_len = max(max_len, k - j - 1);
            res = s.substr(j + 1, max_len);
        }
    }
};

解法二：

#include <string>
using std::string;

class Solution {
public:
    string longestPalindrome(string s) {
        int max_len = 1;
        string res = "";
        const int ls = s.size();
        bool **dp = new bool*[ls];
        for (size_t i = 0; i < ls; ++i)
        {
            dp[i] = new bool[ls];
        };
        res = s.substr(0,1);
        for(int i = 0; i < ls;i++){
            dp[i][i] = true;
        }
        for(int i = 0; i < ls-1;i++){
            if(s[i]==s[i+1]){
                dp[i][i+1] = true;
                if(max_len != 2){
                    max_len = 2;
                    res = s.substr(i,2);
                }
            }
            else dp[i][i+1] = false;
        }
        for(int j = 2; j < ls; j++){
            for(int i = 0; i < ls-j; i++){
                if(dp[i+1][j-1] && (s[i]==s[j])){
                    dp[i][j] = true;
                    int temp = j - i + 1;
                    if(temp > max_len){
                        max_len = temp;
                        res = s.substr(i,temp);
                    }
                }
                else dp[i][j] = false;
            }
        }
        return res;
    }
};