题解 | 密码截取

判断对称

由题可知，需要找到输入字符串的最长对称子串，所以我们首先考虑的是如何确认一个对称字符串。

根据字符串的长度，可以分为奇数和偶数两种方式，两者的主要区别是中心的确认。

String input = “123456”
int i = 0, j = input.length-1;
        while (i <= j) {
            if (input.charAt(i) == input.charAt(j)) {
                if (i < j) {
                    count += 2;
                } else {
                    count++;
                }
                i++;
                j--;
            } else {
                break;
            }
        }

情况分类

1. 如果当前子串就是一个对称子串，就可以直接返回这个子串的长度。
2. 如果当前子串不是一个对称子串，就可以分为两种状态。假如子串的范围为（start，end），那么分别对应以下两种状态的最大值（start+1，end）和（start，end-1）。

代码解答

import java.util.Arrays;
import java.util.Scanner;


public class Main {

    public static int travers(int[][] dp, String input, int start, int end) {

        if (start >= end) return 0;
        if (dp[start][end] != -1) return dp[start][end];
        int count = 0;
        int i = start, j = end;
        while (i <= j) {
            if (input.charAt(i) == input.charAt(j)) {
                if (i < j) {
                    count += 2;
                } else {
                    count++;
                }
                i++;
                j--;
            } else {
                break;
            }
        }
        if (i >= j) {
            dp[start][end] = count;
        } else {
            int re1 = travers(dp, input, start + 1, end);
            int re2 = travers(dp, input, start, end - 1);
            dp[start][end] = Math.max(re1, re2);
        }
        return dp[start][end];
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        scanner.close();

        int[][] dp = new int[input.length()][input.length()];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], -1);
            for (int j = 0; j < dp[0].length; j++) {
                if (i == j) dp[i][j] = 1;
                if (i + 1 == j && input.charAt(i) == input.charAt(j)) dp[i][j] = 2;
            }
        }
        System.out.println(travers(dp, input, 0, input.length() - 1));
    }
}