LeetCode 5:最长回文子串

题目

给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

思路

使用动态规划，首先确定dp含义，dp[i][j]表示区间[i，j]之间的子串是否为回文子串。接下来确定递推公式，回文子串从外到内比较，判断i与j位置字母一致后，若dp[i+1][j-1]为true则可以赋值dp[i][j]，又因为i+1，j-1可能造成i>j的现象，所以需单独判断。初始化，默认dp值为false。确定遍历顺序，因为根据dp[i+1][j-1]推断dp[i][j]，所以应该从下到上，从左到右遍历。

代码

class Solution {
    public String longestPalindrome(String s) {
        int maxlen=0;
        int left=0;
        int right=0;
        boolean [][]dp=new boolean [s.length()][s.length()];//默认为false
        
        for(int i=s.length()-1;i>=0;i--)
        {
            for(int j=i;j<s.length();j++)
            {
                if(s.charAt(i)==s.charAt(j))
                {
                    if(j-i<=1)//i+1，j-1可能造成i>j
                        dp[i][j]=true;
                    else if(dp[i+1][j-1])
                        dp[i][j]=true;
                    
                }
                
                if(dp[i][j]&&j-i+1>maxlen)//保存最大回文子串左右位置
                {
                    maxlen=j-i+1;
                    left=i;
                    right=j;
                }
            }
        }
        return s.substring(left,left+maxlen);
    }
}

反思

①String类型截取字符串函数为substring