题解 | #密码截取#

我觉得中心扩散法比动态规划的思路好理解。

回文字符的特点： ABBA 或者 ABCBA，中心要么是中间两个，要么是最中间的一个(可以看成中间的三个，后续方便编写代码)

思路如下：

1.有两个指针l,r，从0和1的位置向右遍历。r先前进一步，计算一次，l前进一步，计算一次。这里的计算指的是计算以l~r的位置为中心的最长回文字符串的长度(如果l和r字符串不相等就不用考虑)

2.求最长回文字符串的思路很好理解，因为已经知道了中心位置了，所以向左向右依次对比字符就行了，到不同边界或者字符不同的位置就停止。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        if (str.length() == 1) {
            System.out.println(1);
            return;
        }
        int max = 1;
        int l = 0, r = 1;
        for (;;) {
            // 如果 l和r上的字符相等，就往两边走，计算最长回文字符
            if (str.charAt(l) == str.charAt(r)) {
                max = Math.max(max, huiwen(str, l, r));
            }
            ++r;
            if (r >= str.length()) break;
            if (str.charAt(l) == str.charAt(r)) {
                max = Math.max(max, huiwen(str, l, r));
            }
            ++l;
        }
        System.out.println(max);
    }

    // 求以l~r为中心的最长回文字符串长度
    public static int huiwen(String str, int l, int r) {
        int left = l - 1, right = r + 1, count = r - l + 1;
        while (left >= 0 && right < str.length()) {
            if (str.charAt(left) != str.charAt(right)) {
                return count;
            }
            --left;
            ++right;
            count += 2;
        }
        return count;
    }
}