题解 | #最长回文子串#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        // write code here
        // int n = A.size();
        // if ( n == 0) {
        //     return 0;
        // }
        // int res = 0;
        // vector<vector<int>> dp(n, vector<int>(n, 0));
        // for (int i = n - 1; i >= 0; i--) {
        //     for (int j = i ; j < n; j++) {
        //         if (A[i] == A[j]) {
        //             if (j - i <= 1) {
        //                 dp[i][j] = 1;
        //             } else {
        //                 dp[i][j] = dp[i + 1][j - 1];
        //             }
        //         }
        //         if (dp[i][j] == 1) {
        //             res = max(res, j - i + 1);
        //         }
        //     }
        // }
        // return res;
        //使用双指针求法
        // string res="";
        int res = 0;
        for(int i = 0; i< A.size(); i++){
            string str1 = expand(i,i,A);
            string str2 = expand(i,i+1,A);
            res = (res > str1.size()?res : str1.size()) > str2.size()?(res > str1.size()?res : str1.size()):str2.size();
        }
        return res;
    }

    string expand(int left, int right, string str){
        for(;left>=0 && right < str.size() && str[left] == str[right];){
            left--;
            right++;
        }
        return string(str.begin()+left+1,str.begin()+right);
    }
};