【蓝桥杯】15届JAVA研究生组F回文字符串

一、思路

1.这题去年考的时候想的是使用全排列进行尝试，实际不用这么麻烦，只用找到第一个和最后一个非特殊字符串的位置，然后分别向内检查是否对称，向外检查是否对称直到左指针小于0(可以通过添加使其对称)

2.至于如何找到第一个和最后一个非特殊字符串的位置，这里用的栈，其实很多种方法，设两个下标记录，ArrayList等都可以

二、记忆

1.分析题目看看能不能找出规律

三、代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();in.nextLine();for(int i =0;i<n;i++) {String ss = in.nextLine();if(check(ss)) {System.out.println("Yes");}else {System.out.println("No");}}}public static boolean check(String ss) {Deque<Integer> stack = new LinkedList();int n = ss.length();for(int i =0;i<n;i++) {//找到所有非指定字符的位置char temp = ss.charAt(i);if(temp!='l' && temp!='q' && temp!='b') {stack.add(i);}}if(stack.size()==0) {return true;}int left = stack.getLast(),right = stack.getFirst();int l = stack.getLast(),r= stack.getFirst();while(left < right && ss.charAt(left)==ss.charAt(right)) {//两边向中间left++;right--;}while(l>=0 && ss.charAt(l) == ss.charAt(r)) {//两边向两边l--;r++;}if(left>=right && l<0) {return true;}else {return false;}}
}