找出给出的字符串S中最长的回文子串。假设S的最大长度为1000，并且只存在唯一解。

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

复制

"abcba"

复制

"abcba"

动态规划

class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return string字符串
     */
    string longestPalindrome(string str) {
        // write code here
        int n=str.length();
        if (n==0) return "";
        bool dp[n][n];
        fill_n(&dp[0][0],n*n,false);
        int left=0,right=0,maxLen=0;
        for (int j=0;jmaxLen))
                    {
                        left=i;
                        right=j;
                        maxLen=j-i+1;
                    }
            }
            
        }
                    return str.substr(left,right-left+1);
    }
};