要对字符串执行的最小循环（向前或向后）移位以使其成为回文

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 方法扫描现有字符串。我们使用 % n 余数运算符在到达字符串末尾时自动移回字符串开头。请注意，我们应该只检查字符串的一半。

第二，findShift方法。它只是迭代从 0 到 s.length()/2 的所有移位（不需要检查更大的移位，因为它们等于已经检查过的负移位）。在每次迭代中，它都会检查正移和负移。

最后是 main 方法，它读取标准输入并为每个输入行调用 findShift。它会立即输出结果，但如果需要，您可以将其收集到列表中并在最后输出。

要对字符串执行的最小循环（向前或向后）移位以使其成为回文

Minimum cyclic (forward or backward) shifts to be performed to the string to make it a palindrome

java

palindrome

cyclic