5-最长回文子串

5. 最长回文子串

动态规划DP

思想：对于一个子串而言，如果它是回文串，并且长度大于2，那么它首尾的两个字母去掉之后，它仍然是个回文串
状态转移方程： $(s[i]==s[j])\ \&\& \ dp[i+1][j-1]$ ，$dp[i][j]$ 表示子串$s[i..j]$是否是回文
边界条件,即子串的长度为 1 或 2。： $dp(i,i)=true$ 单个字符串， $dp(i,i+1) = (Si==Si+1)$两个字符

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans="";
        for(int k=0;k<n;k++){
            for(int i=0;i+k<n;i++){
                int j = i+k;
                // 先处理两种临界情况
                if(k==0) { //k=0时，j=i, dp[i][j]相当于一个字符串，一定是回文串
                    dp[i][j] = true;
                } else if(k==1){ // k=1时，j=i+1 dp[i][j]相当于连续两个字符，相同时，一定是回文串
                    dp[i][j] = (s.charAt(i)==s.charAt(j));
                } else{ // k>1 时，需满足状态转移方程，dp[i,j] = dp[i+1][j-1] && (si==sj)
                    dp[i][j] = (s.charAt(i)==s.charAt(j) && dp[i+1][j-1]);
                }
                if(dp[i][j] && k+1>ans.length()){ //更新回文串长度
                    ans = s.substring(i, i+k+1); // 注意子串方法的具体用法
                }
            }
        }
        return ans;
    }
}

时间复杂度：$O(n^2)$ 其中n是字符串长度，动态规划的状态总数为$O(n^2)$，对于每个状态，我们需要转移的实际为$O(1)$

空间复杂度: $O(n^2)$ 即存储动态规划需要的空间

中心扩展

思想

前提条件:
- 根据状态转移方程，可以发现所有的状态，在转移的时候可能性都是唯一的。也就是说，我们可以从每一种边界情况开始扩展，也可以得出所有状态对应的答案。
- 边界情况，对应的子串实际上就是我们扩展出的回文串的回文中心
本质：
- 枚举所有的回文中心，并尝试扩展，直到无法扩展为止，此时的回文串长度即为回文中心下的最长回文串长度。

//中心扩展
    public String longestPalindrome(String s) {
        if(s==null || s.length()==0) return "";
        int start = 0, end=0; // 初始化最大回文串的起点和终点
        // 遍历每个位置，当做中心
        for(int i=0;i<s.length();i++){
            // 分别拿到奇数偶数的回文串长度
            int len_odd = expandCenter(s,i,i);
            int len_even = expandCenter(s,i,i+1);
            int len = Math.max(len_odd,len_even);
            // 计算对应最大回文子串的起点和终点
            if(len > end-start){
                /**
                    这里为什么要len-1？ ，因为for循环是从0开始的，
                    如果是奇数回文，假设有个回文是3个，那么len=3，此时中心i是下标1（从0开始），那么(len-1)/2和len/2的结果都是1，因为整数会向下取整
                    但是如果是偶数回文，假设和有个回文是4个，那么len=4，此时的中心是一条虚线，但是i的位置在1，因为s是从左向右遍历的，
                    如果从左向右i的位置就会在2，这个时候 (len-1)/2 =1 ,len/2=2 ,很明显为了保证下标正确，我们需要的是(len-1)/2，原因是i在中心线的左边一位。
                    所以要少减一个1
                 */
                start = i-(len-1)/2;
                end = i+len/2;
            }
        }
        return s.substring(start, end+1);//注意这里end+1是因为java自带左闭右开的原因
    }

    private int expandCenter(String s,int left, int right){//起始的左右边界
        // left = right的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left+1的时候，此时回文中心是一个空隙，回文串的长度是偶数
        // 跳出循环的时候恰好满足 s.charAt(left)!=s.charAt(right)
        while(left >=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1; //回文串的长度是right-left+1-2 = right -left -1
    }