Минимальные циклические (вперед или назад) сдвиги, которые необходимо выполнить для строки, чтобы сделать ее палиндром

Question

Ниже приводится описание проблемы и решение. Два теста не удались для меня. Помогите мне понять это.

Строка называется палиндром, если она читает то же самое с обоих концов. Учитывая строку S, вам разрешено выполнять циклические смены. Более формально вы можете выбрать любого персонажа с любого конца (головы или хвоста), и вы можете добавить этот символ на другом конце. Например, если строка равна "abc", то, если мы выполняем смену с использованием символа в верхнем положении, строка становится "bca". Аналогично, если мы выполняем сдвиг с использованием символа в хвосте, тогда входная строка становится "cab". Ваша задача - узнать минимальное количество сдвигов, необходимых для создания данной строки, палиндрома. В случае, если мы не можем преобразовать строку в палиндром, тогда напечатайте -1.

Формат ввода: Первая строка начинается с T т.е. количеством тестовых примеров, а затем T линии будут следовать за каждый из которых содержит строку S.

Формат вывода: Распечатайте минимальное количество циклических сдвигов для каждой строки, если это можно сделать палиндром, иначе -1.

Ограничения: 1<=T<=100, 1<=|S|<=300, S будет содержит только строчные алфавиты ('a'-'z').

Пример ввода и вывода

Входной

4 
abbb 
aaabb 
aabb 
abc 

Выход

-1 
1 
1 
-1 

Объяснение: Для случая испытания 2 (aaabb): сдвиг символа в хвост к голове и результатом будет «baaab», который является палиндром. Это операция, которая требует минимального количества сдвигов, чтобы сделать данную строку палиндром.

Для тестового примера 3 (aabb): Один из способов преобразовать заданную строку в палиндром, смещение символа в головы до хвоста, и результат будет "abba", который является палиндром. Другим способом является перемещение символа в хвост к голове, и результат будет "baab", который также является палиндром. Оба требуют только одну смену.

public class cyclic { 

    static boolean flag = false; 

    // fn to check if string is palindrome 
    static boolean ispal(String s) { 
     String reverse = ""; 
     int length = s.length(); 
     for (int i = length - 1; i >= 0; i--) 
      reverse = reverse + s.charAt(i); 
     reverse = reverse.trim(); 
     if (s.equals(reverse)) { 
      flag = true; 
      return true; 
     } else { 
      return false; 
     } 
    } 

    // fn to perform front shift 
    static int frontshift(String str) { 
     int count = 0; 
     String element = ""; 
     String s1[] = str.split(""); 
     Deque<String> dequeA = new LinkedList<String>(); 
     for (int i = 1; i < s1.length; i++) { 
      dequeA.add(s1[i]); 
     } 
     while (!ispal(str)) { 
      if (count <= str.length()) { 
       element = ""; 
       String firstElement = dequeA.removeFirst(); 
       dequeA.addLast(firstElement); 
       for (String object : dequeA) { 
        element = element + object; 
       } 
       str = element; 
       count++; 
      } else { 
       break; 
      } 
     } 
     return count; 
    } 

    // fn to perform backshift 
    static int backshift(String str) { 
     int count = 0; 
     String element = ""; 
     String s1[] = str.split(""); 
     Deque<String> dequeA = new LinkedList<String>(); 
     for (int i = 1; i < s1.length; i++) { 
      dequeA.add(s1[i]); 
     } 
     while (!ispal(str)) { 
      if (count <= str.length()) { 
       element = ""; 
       String firstElement = dequeA.removeLast(); 
       dequeA.addFirst(firstElement); 
       for (String object : dequeA) { 
        element = element + object; 
       } 
       str = element; 
       count++; 
      } else { 
       break; 
      } 
     } 
     return count; 
    } 

    public static void main(String args[]) throws IOException { 
     BufferedReader br = 
       new BufferedReader(new InputStreamReader(System.in)); 
     List<Integer> list = new ArrayList<Integer>(); 
     int range = Integer.parseInt(br.readLine()); 
     for (int i = 0; i < range; i++) { 
      String s = br.readLine(); 
      int l1 = frontshift(s); 
      int l2 = backshift(s); 
      if (flag == true) { 
       if (l1 <= l2) { 
        list.add(l1); 
       } else { 
        list.add(l2); 
       } 
      } else { 
       list.add(-1); 
      } 
      flag = false; 
     } 
     for (Integer integer : list) { 
      System.out.println(integer); 
     } 
    } 
} 

Answer 1

Я решил свою задачу, не основанную на коде:

import java.util.Scanner; 

public class PalyndromeTest { 
    static boolean isPalyndrome(String s, int shift) { 
     int n = s.length(); 
     if(shift < 0) shift+=n; 
     for(int pos = 0; pos < n/2; pos++) { 
      if(s.charAt((pos+shift)%n) != s.charAt((n-pos-1+shift)%n)) 
       return false; 
     } 
     return true; 
    } 

    static int findShift(String s) { 
     for(int shift = 0; shift <= s.length()/2; shift++) { 
      if(isPalyndrome(s, shift) || isPalyndrome(s, -shift)) 
       return shift; 
     } 
     return -1; 
    } 

    public static void main(String[] args) { 
     Scanner s = new Scanner(System.in); 
     int count = s.nextInt(); 
     s.nextLine(); 
     for(int i=0; i<count; i++) { 
      System.out.println(findShift(s.nextLine())); 
     } 
    } 
} 

Во-первых, isPalyndrome метод. Он проверяет, является ли строка палиндром и работает с положительными или отрицательными сдвигами. Обратите внимание, что, например, для строки длиной 5, shift = -1 совпадает с shift = 4. Мы не создаем никаких новых строк, мы просто просматриваем существующий, используя метод String.charAt. Мы используем оператор остатка, чтобы автоматически вернуться к началу строки, когда достигнут конец строки. Обратите внимание, что мы должны проверять только половину строки.

Во-вторых, метод findShift.Он просто перебирает все сдвиги от 0 до s.length()/2 (больших сдвигов нет необходимости проверять, поскольку они равны уже отмеченным отрицательным сдвигам). На каждой итерации он проверяет как положительный, так и отрицательный сдвиг.

Наконец, метод main, который считывает стандартный ввод и вызывает findShift для каждой строки ввода. Он выводит результат немедленно, хотя, если вы хотите, вы можете собрать его в список и вывести в конце.