题目

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

题解

• dp。先初始化长度为1和长度为2的串。再依次算长度为3，4，5...。
• 当找到回文串时，若长度比当前记录的回文串长度大，则更新起始位置和最大长度，最终用substring返回子串。
• 时间复杂度O(n^{2)。空间复杂度O(n}2)。

todo

还可以用中心扩展法、和马拉车法，待学习。

代码

class Solution {

    public String longestPalindrome(String s) {

        if(s==null||s.length()<2){return s;}

        int len=s.length();

        boolean[][] dp = new boolean[len][len];

        for(int i=0;i<len;++i){

            dp[i][i]=true;

            if(i>0){

                dp[i][i-1]=true;

            }

        }

        int beg=0;

        int maxLen=1;

        for(int l=2;l<=len;++l){

            for(int i=0;i+l-1<len;++i){

                int j=i+l-1;

                if(s.charAt(i)==s.charAt(j)&&dp[i+1][j-1]){

                    dp[i][j]=true;

                    if(l>maxLen){

                        maxLen=l;

                        beg=i;

                    }

                }

            }

        }

        return s.substring(beg,beg+maxLen);

    }

}