Description
牛客网 校招真题 回文
Solving Ideas
计算以str[str.length() - 1]为结尾的最大的回文长度，从而判断最少需要追加多少个字母才能使整个串成为回文。
Solution
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/*** @author wylu*/public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));char[] str = br.readLine().toCharArray();//以str[str.length() - 1]为结尾的最大的回文长度int maxLen = 0;for (int i = 0; i < str.length; i++) {if (str.length - i > maxLen && isPalindrome(str, i, str.length - 1)) {maxLen = str.length - i;}}System.out.println(2 * str.length - maxLen);}private static boolean isPalindrome(char[] str, int begin, int end) {for (int i = begin, j = end; i < j; i++, j--) {if (str[i] != str[j]) return false;}return true;}}
import java.util.Scanner;/*** @author wylu*/public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {char[] str = scanner.next().toCharArray();//dp[0]: 以str[str.length() - 1]为结尾的最大的回文长度int[] dp = {0};for (int i = (str.length - 1) / 2; i < str.length; i++) {//以str[i]为中心的回文的长度expandAroundCenter(str, i, i, dp);//以str[i]-str[i+1]之间的间隔为中心的回文的长度expandAroundCenter(str, i, i + 1, dp);}int res = (str.length - dp[0]) + str.length;System.out.println(res);}}private static void expandAroundCenter(char[] str, int i, int j, int[] dp) {for (; i >= 0 && j < str.length && str[i] == str[j]; i--, j++) {if (j == str.length - 1) dp[0] = Math.max(dp[0], j - i + 1);}}}
如果觉得《牛客网 校招真题 京东 回文》对你有帮助，请点赞、收藏，并留下你的观点哦！
