题解 | #最长回文子串#

使用双指针法进行 ~ 操作见代码注释。

import java.util.Scanner;

/*
    使用双指针的办法
    ---------------------------
    ...| perv | curr | next |...
    ---------------------------
         👆            👆
    <-- f_pointer    r_pinter -->
    
    使用一个指针遍历链表，遍历的过程中，检查当前指向元素与
    左、右以及指针位置的左右他们是否有回文的情况
	即 (perv curr), (curr next), (perv next)
    
    如果有回文的情况，设置两个新指针，分别指向回文的左右两个字符
    然后开始前进/后退，同时比较指向的两个元素的值是否存在回文

    直到不再回文了，记录回文次数与最大值做比较，取大的。
*/
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char[] chars = s.toCharArray();
        int len = chars.length;
        // 最大回文
        int max = 0;
        // 这里注意越界条件判断
        for(int i = 1; i < len - 1; i++) {
            char perv = chars[i-1];
            char curr = chars[i];
            char next = chars[i+1];
            // 前进指针
            int f_pointer = 0;
            // 后退指针
            int r_pointer = 0;
            // 返回值
            int calv = 0;
            if(perv == curr) {
                // 当前字符串和它之前的回文
                f_pointer = i;
                r_pointer = i - 1;
                calv = calcVal(chars, len, f_pointer, r_pointer);
            } else if(curr == next) {
                // 当前字符串和它后边的回文
                f_pointer = i + 1;
                r_pointer = i;
                calv = calcVal(chars, len, f_pointer, r_pointer);
            } else if(perv == next) {
                // 当前字符串的前后回文
                f_pointer = i + 1;
                r_pointer = i - 1;
                calv = calcVal(chars, len, f_pointer, r_pointer);
                // 这里之所以 + 1 是因为要把 curr 字符也算在回文里面
                calv ++;
            }
            if(max < calv) max = calv;
        }
        System.out.println(max);
    }

    // 在元素中移动并且查找回文数值
    private static int calcVal(char[] chars, int length,int f_pointer, int r_pointer) {
        // 设置一个计数器
        int count = 0;
        /*
            只要前进和后退索引不到它们的阈值(前进不能超过 len -1,后进不能小于 0)，
            并且 前进索引和后退索引的值，只要相同，就说明在回文，继续操作
        */
        while (f_pointer < length && r_pointer >= 0 && chars[f_pointer] == chars[r_pointer]) {
            // 步长为 2 因为每次两个指针各指一个元素
            count += 2;
            // 前进
            f_pointer ++;
            // 后退
            r_pointer --;
        }
        return count;
    }
}