0

以下は、問題の説明と解決策です。2 つのテスト ケースが失敗しました。私がそれを理解するのを手伝ってください。

文字列が両端から同じように読める場合、その文字列は回文であると言われます。stringSを指定すると、巡回シフトを実行できます。より正式には、任意の端 (頭または尾) から任意の 1 文字を選択し、その文字をもう一方の端に追加できます。たとえば、文字列が の場合、"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) の場合: 指定された文字列を回文に変換する 1 つの方法は、先頭の文字を末尾にシフトすることです。結果"abba"は、回文である になります。別の方法は、末尾の文字を先頭に移動することであり、結果は になります"baab"。これも回文です。どちらも 1 シフトだけで済みます。

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);
        }
    }
}
4

1 に答える 1

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標準入力を読み込んでfindShiftfor each 入力行を呼び出すメソッド。結果はすぐに出力されますが、必要に応じてリストにまとめて最後に出力することもできます。

于 2015-08-21T08:29:32.553 に答える