[HackerRank]迴文索引位置(Palindrome Index)

題目描述

給定一個由小寫英文字母組成的字串，請找出要移除哪個索引位置的字元才能讓字串符合回文的格式。如果字串原本就已經是回文了，直接輸出-1即可。

原題網址

輸入格式

第一行為一個整數T，表示有幾組測試資料，範圍在1到20之間(包含1和20)。接下來的T行每行都是要測試的字串，字串長度在1到100005之間(包含1和100005)，字元都是小寫英文字母。

輸出格式

分行輸出要刪除哪個索引值的字元才能讓字串符合回文格式，如果字串原本就是回文，輸出「-1」。

範例輸入

範例輸出

額外解釋

第一個測試字串「aaab」，移除索引3的「a」之後會變成「aab」，符合回文格式，所以輸出「3」。

第二個測試字串「baa」，移除索引0的「b」之後會變成「aa」，符合回文格式，所以輸出「0」。

第三個測試字串「aaa」，原本就符合回文格式，所以輸出「-1」。

解題概念

這題首先需要注意的是輸入的字串長度可能會高達100005，因此如果要用很直覺暴力的方式來解(先判斷是不是回文，如果不是就直接從索引0開始，把字元移除後再看看是不是回文)是行不通的，因為計算時間會變得太長。

在這邊可以先計算出索引的中間值，並檢查從索引0到中間值-1的字元是否和以中間為基準的對面字元(例如目前正在檢查索引0，對面字元就是字串的最後一個字元；換句話說，若目前正在檢查索引i，對面的字元的索引值就是「字串長度-1-i」)一樣。如果都一樣，表示這個字串原本就是回文，直接輸出「-1」；如果不同，則另外記目前的索引值，並繼續檢查之後的字元是否和以中間為基準但索引值要再減一的對面字元(若之後正在檢查索引i，對面的字元的索引值就是「字串長度-i」)一樣，因為此時是在判斷如果目前的索引值的字元被移除的情況下，字串是否符合回文格式。由於題目一定會輸入符合回文格式，或是刪除一個字元之後會符合回文格式的字串，所以如果往後檢查結束時，發現字串確實符合回文格式，則可以直接輸出目前的索引值，也就是當初檢查時所找到地不符合回文格式的字元就是要刪除的字元。而如果往後檢查還是發現字串不符合回文格式的話，表示刪除目前索引值的字元也沒辦法讓字串符合回文格式，因此可以推定目前索引值的對面索引值的字元就是要刪除的字元。

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(final String[] args) {
        final Scanner sc = new Scanner(System.in);

        int t = Integer.parseInt(sc.nextLine());
        while (t-- > 0) {
            final char[] s = sc.nextLine().toCharArray();
            final int length = s.length;
            final int length_dec = length - 1;
            final int length_half = length / 2;
            int i = 0;
            for (; i < length_half; ++i) {
                if (s[i] != s[length_dec - i]) {
                    break;
                }
            }
            if (i == length_half) {
                System.out.println(-1);
                continue;
            }
            final int index = i++;
            for (; i < length_half; ++i) {
                if (s[i] != s[length - i]) {
                    break;
                }
            }
            System.out.println(i == length_half ? index : length_dec - index);
        }
    }
}