题解 | 最长回文子串

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param A string字符串 
 * @return int整型
 */
#include <stdbool.h>
int getLongestPalindrome(char* A ) {
    // write code here
    int length=strlen(A);
    if(length==0)return 0;
    int max=1;
    bool dp[length][length];//表示从A[i]到A[j]是否是回文子串（true/false)
    memset(dp,false,sizeof(dp));
    for(int i=0;i<length;i++){//单个字符均可视为长度为1的回文子串
        dp[i][i]=true;
    }
  //长度为二的回文子串，就是相邻的两个字符
    for(int i=0;i<length-1;i++){
        if(A[i]==A[i+1]){
            dp[i][i+1]=true;
            max=2;
        }
    }
  //长度大于3的回文子串，考虑从3到最长为length的情况，j是回文子串最后一个字符的位置
    for(int len=3;len<=length;len++){
        for(int i=0;i<=length-len;i++){
            int j=i+len-1;
            if(A[i]==A[j]&&dp[i+1][j-1]==true){
                dp[i][j]=true;
                max=max>len?max:len;
            }
        }
    }
    return max;
}