题解 | #最长回文子串#注意边界
最长回文子串
https://www.nowcoder.com/practice/12e081cd10ee4794a2bd70c7d68f5507
import java.util.*; // 这个题感觉没法做到时间复杂度为O(n),当然也可能存在。看了另外一个兄弟的解法,空间复杂度降低到O(1),省略了dp数组,挺好! public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 String raw = in.nextLine(); int max = 0; //时间复杂度是O(n^2),空间复杂度是O(n) boolean[] dp = new boolean[raw.length() / 2 + 1]; dp[0] = true; if(raw.length()==1){ max = 1; } for (int i = 0; i <raw.length()-1; i++) { if (raw.charAt(i) != raw.charAt(i + 1)) { for (int j = 1; j < raw.length() / 2 + 1; j++) { if (i + j > raw.length()-1 || i - j < 0) { dp[j] = false; }else{ dp[j] = dp[j - 1] && raw.charAt(i + j) == raw.charAt(i - j); } } int m = dp.length-1; while (m >= 0) { if (dp[m] == true) { max = Math.max(max, m*2+1); break; } m--; } } else { for (int j = 1; j < raw.length() / 2 + 1; j++) { if (i + 1 + j > raw.length()-1 || i - j < 0) { dp[j] = false; }else{ dp[j] = dp[j - 1] && raw.charAt(i + 1 + j) == raw.charAt(i - j); } int m = dp.length-1; while (m >= 0) { if (dp[m] == true) { max = Math.max(max, m*2+2); break; } m--; } } } } System.out.println(max); // 时间复杂度是O(n),空间复杂度是O(2^n) // int maxFinal = 0; // for (int i = 0; i < raw.length(); i++) { // max = Math.max(judgePalindrome1(raw, i, i) + 1, judgePalindrome2(raw, i, i)+1); // maxFinal = Math.max(max, maxFinal); // } // System.out.println(maxFinal); } // public static int judgePalindrome1(String raw, int left, int right) { // int num = 0; // if (--left >= 0 && ++right <= raw.length() - 1) { // if (raw.charAt(left) == raw.charAt(right)) { // num = 2 + Math.max(judgePalindrome1(raw, left, right), judgePalindrome2(raw, // left, right)); // } // } // return num; // } // public static int judgePalindrome2(String raw, int left, int right) { // int num = 0; // int right1 = right + 1; // int right2 = right + right - left + 1; // if (right2 < raw.length() - 1) { // if (raw.substring(left, right + 1).equals(raw.substring(right1, right2 + 1))) { // num = right - left + 1 + Math.max(judgePalindrome1(raw, left, right2), // judgePalindrome2(raw, left, right2)); // } // } else if (right2 == raw.length() - 1) { // if (raw.substring(left, right + 1).equals(raw.substring(right1))) { // num = right - left + 1 + Math.max(judgePalindrome1(raw, left, right2), // judgePalindrome2(raw, left, right2)); // } // } // return num; // } }