Java写题解的第3天 | #密码截取#

问题等价于leetcode 第五题，可以参考leetcode的官方题解
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = "";
        while ((s = br.readLine()) != null) {
            System.out.println(validLen(s));
        }
        br.close();
    }

    public static int validLen(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for(int i = 0; i < len - 1; i++) {
            dp[i][i] = true;
            if (s.charAt(i) == s.charAt(i+1)) {
                dp[i][i+1] = true;
            }
        }
        for (int m = len - 2; m > -1; m--) {
            for (int n = m + 2; n < len; n++) {
                if (dp[m+1][n-1] && s.charAt(m) == s.charAt(n)) {
                    dp[m][n] = true;
                }
            }
        }
        int ans = 1;
        for (int p = 0; p < len; p++) {
            for (int q = p + 1; q < len; q++) {
                if (dp[p][q]) {
                    ans = (ans > q - p + 1)? ans: (q - p + 1);
                }
            }
        }
        return ans;
    }
}