5. 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.

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

Example:

Input: "babad"Output: "bab"Note: "aba" is also a valid answer.

 

Example:

Input: "cbbd"Output: "bb"

class Solution {public:    string longestPalindrome(string s) {                int maxLength=0;        int index;        const int n = s.size();        int **arr;        arr = new int*[n];        for (int i = 0; i < n; i++) {            arr[i] = new int[n];            memset(arr[i], 0, sizeof(int)*n);        }        for (int k = 0; k < n; k++)        {            for (int i = 0; i < n - k; i++)            {                int j = i + k;                if (k == 0)                    arr[i][j] = 1;                else if (k == 1 && s[j] == s[i])                    arr[i][j] = 2;                else if (s[j] == s[i] && arr[i + 1][j - 1] != 0)                    arr[i][j] = arr[i + 1][j - 1] + 2;                if (arr[i][j] > maxLength)                 {                    maxLength = arr[i][j];                    index = i;                }            }        }    /*    for (int i = 0; i < n; i++)        {            for (int j = 0; j < n; j++)            {                cout << arr[i][j] << " ";            }            cout << endl;        }*/        return s.substr(index,maxLength);    }};int main(){    Solution solution;    string s = "cbbdbb";    string result = solution.longestPalindrome(s);    cout << result;    system("pause");    return 0;}

别人解法

class Solution {public:    string longestPalindrome(string s) {        if (s.empty()) return "";        if (s.size() == 1) return s;        int min_start = 0, max_len = 1;        for (int i = 0; i < s.size();) {            if (s.size() -i <= max_len / 2) break;            int j = i, k = i;            while (k < s.size() && s[k+1] == s[k]) k++;            i = k+1;            while(k < s.size() - 1 && j > 0 && s[k + 1] == s[j - 1]) { ++k; --j;}            int new_len = k - j + 1;            if (new_len > max_len) {min_start = j; max_len = new_len;}        }        return s.substr(min_start, max_len);            }};