题解 | #密码截取#
密码截取
http://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1
就是最长回文子串问题
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String origin = ""; while ((origin = in.readLine()) != null){ System.out.println(longestPalindromic2(origin).length()); } } /** * 输出字符串的最长回文子串 * @param str 字符串 * @return 回文串 */ public static String longestPalindromic2(String str){ // 回文串开始位置 int start = 0; // 回文串最大长度 int maxLen = 0; char[] chars = str.toCharArray(); // 如果为奇数 当前位置的前一个数和后一个数一定相等 for (int i = 0; i < chars.length; i++) { for (int j = 0; i - j >= 0 && i + j < chars.length; j++) { if (chars[i - j] == chars[i + j]){ // 获取最大长度,高位索引 - 低位索引 + 1 int len = (i + j) - (i - j) + 1; // 当前长度比最大长度还大,覆盖最大长度,开始位置为i-j if (len > maxLen){ maxLen = len; start = i - j; } }else { // 不是回文,直接跳出内层循环 break; } } } // 如果为偶数,表示中间的两个元素向外扩展时对称的 if (chars.length > 1){ for (int i = 0; i < chars.length; i++) { for (int j = 0; i - j >= 0 && i + j + 1 < chars.length; j++) { if (chars[i - j] == chars[i + j + 1]){ // 获取最大长度,高位索引 - 低位索引 + 1 int len = (i + j + 1) - (i - j) + 1; // 当前长度比最大长度还大,覆盖最大长度,开始位置为i-j if (len > maxLen){ maxLen = len; start = i - j; } }else { // 不是回文,直接跳出内层循环 break; } } } } return str.substring(start, start + maxLen); } }