最长回文子串

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
        // write code here

        // 填充字符串：123 -> #1#2#3#
        // 注意，两边也要有#，这样直接除以2就能返回结果，否则还要分类讨论
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < A.length(); i++) {
            sb.append('#');
            sb.append(A.charAt(i));
        }
        sb.append('#');
        String newS = sb.toString();

        // 统计最长回文子串长度
        // 基础写法 - 空间复杂度O(1)，时间复杂度O(N2)；
        /*
        int max = 0;
        for (int i = 0; i < newS.length(); i++) {
            int l = i;
            int r = i;
            int len = 0;
            while (l >= 0 && r < newS.length() && newS.charAt(l) == newS.charAt(r)) {
                if (newS.charAt(l) != '#') {
                    if (l == r) {
                        len++;
                    } else if (l != r && newS.charAt(l) != '#') {
                        len += 2;
                    }
                }
                l--;
                r++;
            }
            if (len > max) {
                max = len;
            }
        }
        */

        // Manacher算法：空间复杂度O(N)，时间复杂度O(N)
        
        // 设置一个长度为n的数组：表示以当前元素为中心的回文半径；
        int[] lens = new int[newS.length()];
        // 设置两个全局的变量：当前最大回文字串的右边界与中心点
        // 初始化成-1，表示第一个元素就要外扩
        int c = -1;
        int b = -1;
        int max = 0;
        for (int i = 0; i < newS.length(); i++) {
            if (i > b) {
                // 1.当前元素超出了当前最大回文子串的右边界
                // 直接双指针暴力扩
                int left = i;
                int right = i;
                int len = 0;
                while (left >= 0 && right < newS.length() && newS.charAt(left) == newS.charAt(right)) {
                    if (left == right) {
                        len++;
                    } else if (left != right) {
                        len += 2;
                    }
                    left--;
                    right++;
                }
                if (len > max) {
                    // 若当前回文子串突破了最大值，则更新c和b
                    max = len;
                    c = i;
                    b = right - 1;
                }
                // 无论如何，将当前i位置回文子串长度计入lens数组中对应i位置
                lens[i] = right - 1 - i;
            } else {
                // 2.当前元素没有超过当前最大回文子串的右边界
                // 必然能找到i相对于c的对称元素iSym，观察iSym的回文子串情况，进行分类讨论
                int iSym = c * 2 - i;
                int iSymR = lens[iSym];
                int bSym = c * 2 - b;
                if ((iSym - iSymR) > bSym) {
                    // 2.1 iSym的回文区域完全包含在bSym...c...b内
                    // 说明i位置的元素回文子串必然没有突破b的限制，因此不必进行统计，直接沿用iSym的半径和直径，且不必更新c和b；
                    lens[i] = lens[iSym];
                } else if ((iSym - iSymR) < bSym) {
                    // 2.2 iSym的回文区域超出了bSym...c...b范围
                    // 说明iSym的回文超出bSym的部分必然没有对应在b处，要不然bSym和b的范围还会再此基础上再扩大，与当前确定的bSym和b范围相冲突，因此不必进行统计，i位置的回文半径就是i到b之间的部分，且不必更新c和b；
                    lens[i] = b - i;
                } else {
                    // 2.3 i’的回文区域正好达到了bSym之上：
                    // 说明i到b的部分必然是i位置元素的回文，这部分不必验证，直接验证外面的元素就好，再根据验证的情况决定是否更新c和b：
                    int right = b + 1;
                    int left = i * 2 - right;
                    int len = (b - i) * 2 + 1;
                    while (left >= 0 && right < newS.length() && newS.charAt(left) == newS.charAt(right)) {
                        if (left == right) {
                            len++;
                        } else if (left != right) {
                            len += 2;
                        }
                        left--;
                        right++;
                    }
                    if (len > max) {
                        // 若当前回文子串突破了最大值，则更新c和b
                        max = len;
                        c = i;
                        b = right - 1;
                    }
                    // 无论如何，将当前i位置回文子串长度计入lens数组中对应i位置
                    lens[i] = right - 1 - i;
                }
            }
        }
        // 记得除以2排除#字符
        return max / 2;
    }
}

public int getLongestPalindrome (String A) {
    // write code here
    int maxLen=0;
    for(int i=0;i<A.length();i++){
        int p1=i ,p2=i;
        while(p2+1<A.length() && A.charAt(p2)==A.charAt(p2+1)){
            p2++;
        }
        i=p2;
        while(p1-1>=0 && p2+1<A.length() && A.charAt(p1-1)==A.charAt(p2+1)){
            p1--;
            p2++;
        }
        maxLen=Math.max(maxLen ,p2-p1+1);
    }
    return maxLen;
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
  // write code here
        if (A == null || A.isEmpty()) {
            return 0;
        }
        int len = A.length();
        int max = 1;
        for (int i = 0; i < len; i++) {
            StringBuilder str = new StringBuilder(String.valueOf(A.charAt(i)));
            for (int j = i + 1; j < len; j++) {
                StringBuilder append = str.append(A.charAt(j));
                StringBuilder reverse = new StringBuilder(append);
                reverse.reverse();
                if (append.toString().contentEquals(reverse)) {
                    if (append.length() > max) {
                        max = append.length();
                    }
                }
            }
        }
        return max;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
        // write code here
        int n = A.length();
        int max = 1;
        for (int i = 0; i < n; i++) {
            for (int j = n - 1; j > i ; j--) {
                String sub = A.substring(i, j + 1);
                StringBuffer a = new StringBuffer(sub).reverse();
                if (sub.equals(a.toString())) {
                    max = Math.max(max, a.length());
                }
            }
        }
        return max;
    }
}

public int getLongestPalindrome(String s) {
    StringBuilder sb = new StringBuilder(s);
    int n = sb.length();
    boolean[][] dp = new boolean[n][n];
    int res = 1;
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    for (int j = 1; j < n; j++) {
        for (int i = j - 1; i >= 0; i--) {
            if (j - i <= 2 && sb.charAt(i) == sb.charAt(j)) {
                dp[i][j] = true;
                res = Math.max(res, j - i + 1);
            } else if (sb.charAt(i) == sb.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1];
                if (dp[i][j]) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }
    }
    return res;
}

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
        // write code here
        if (A.length() == 1) return 1;
        if (A.isEmpty()) return 0;
        int maxCount = 0;
        for (int i = 0; i < A.length(); i++) {
            int j = 0;
            while (j <= i) {
                String temp = A.substring(j, A.length() - i + j);
                String newTemp = String.valueOf(new StringBuilder(temp).reverse());
                if (temp.equals(newTemp) && temp.length() > maxCount) {
                    return temp.length();
                }
                j++;
            }
        }
        return 0;
    }
}

import java.util.*;

public class Solution {
    public int getLongestPalindrome (String A) {
        // write code here
        int maxlen = 1;
        int n = A.length();
        boolean[][] dp = new boolean[n][n];

        for(int right = 1; right < n; right++){
            for(int left = 0; left <= right; left++){
                //两端字符不相同，必定不是回文，直接略过
                if(A.charAt(left) != A.charAt(right))
                    continue;
                
                //当窗口内只有1个字符或两个字符时候，一定是回文。如："a", "aa", 其实这里相当于起始条件。
                if(right-left<=1){
                    dp[left][right] = true;
                }else{
                    dp[left][right] = dp[left+1][right-1];
                }
                
                if(dp[left][right] && right-left+1>maxlen){
                    maxlen = right-left+1;
                }
            }
        }
        return maxlen;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
        // write code here
        String reverse = new StringBuilder(A).reverse().toString();
        int result = 0;
        for (int i = 0; i < A.length(); i++) {
            if (result > A.length() - i) {
                break;
            }
            for (int j = i + 1 + result; j <= A.length(); j++) {
                String substring = A.substring(i, j);
                if (reverse.contains(substring)) {
                    // 求出公共子串
                    if (reverse.substring(reverse.length() - j,
                                          reverse.length() - i).equals(substring)) {
                        // 如果位置满足回文串的相关性，那么就是回文串没错了
                        result = substring.length();
                    }
                } else {
                    break;
                }
            }
        }
        return result;
    }
}

public int getLongestPalindrome (String A) {
        if(A==null){
            return 0;
        }
        if(A.length()<2){
            return A.length();
        }
        int ans=1;
        for(int i=0;i<A.length();i++){
            for(int j=i+1;j<A.length();j++){
                String str=A.substring(i,j+1);
                if(str.equals(new StringBuilder(str).reverse().toString())){
                    ans=Math.max(ans,str.length());
                }
            }
        }
        return ans;
    }

可能我只会简单粗暴的方法

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
        if (A.length() <= 1) {
            return A.length();
        }
        int max = 1;
        for (int i = 0; i < A.length(); i++) {
            for (int j = i + 1; j < A.length(); j++) {
                String substring = A.substring(i, j + 1);
                if (substring.equals(new StringBuilder(substring).reverse().toString())) {
                    max = Math.max(max, substring.length());
                }
            }
        }
        return max;
    }
}

    /**
     * ☆☆☆☆☆
     * 最长回文子串
     * 中心扩展 + 动态规划 + Manacher
     */
    private static void longestPalindrome2() {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.nextLine();
            // 字符间隔及两边插入#，方便统一中心扩展方式的两种情况：中心在元素上和中心在元素间
            StringBuilder sb = new StringBuilder("#");
            for (int i = 0; i < s.length(); i++) {
                sb.append(s.charAt(i)).append("#");
            }
            // 数组用于存插入#后，当前元素为中心的最大回文半径（自身算1）
            // 最终的最大回文长度是该半径-1（该半径多出来的#，比另一边的原字符多一）
            int[] arr = new int[sb.length()];
            // 已知的所有回文串的最右边界+1
            int maxPos = 0;
            // 边界最右的回文串的中心
            int index = 0;
            for (int i = 0; i < sb.length(); i++) {
                if (i < maxPos) {
                    // 此处是关键，i相对index的对称位置2*index-i，直接参与计算，避免重复计算
                    arr[i] = Math.min(arr[2 * index - i], maxPos - i);
                } else {
                    arr[i] = 1;
                }
                // 在已有基础上继续扩展判断，越界判断，以及两边字符判断
                while (i - arr[i] >= 0 && i + arr[i] < sb.length() && sb.charAt(i - arr[i]) == sb.charAt(i + arr[i])) {
                    arr[i]++;
                }
                // 更新maxpos和index
                if (i + arr[i] > maxPos) {
                    maxPos = i + arr[i];
                    index = i;
                }
            }
            int max = 0;
            for (int i = 0; i < sb.length(); i++) {
                max = Math.max(max, arr[i]);
            }
            // 最长回文串的长度
            System.out.println(max - 1);
            // 最长回文串
            for (int i = 0; i < sb.length(); i++) {
                if (max == arr[i]) {
                    String result = sb.substring(i - arr[i] + 1, i + arr[i]).replace("#", "");
                    System.out.println(result);
                    break;
                }
            }
        }
    }