題目描述

多斯拉其語正在計劃發動一個攻擊來竄取羅伯特國王的王位。羅伯特國王從烏鴉那得知了這場陰謀。並計劃鎖住敵人唯一能通過的那扇門。然而,要鎖住那扇門必須要有一個鑰匙,這個鑰匙是一個回文字串的變位詞。請幫助他判斷一個字串的變位詞是否為回文。



原題網址

https://www.hackerrank.com/challenges/game-of-thrones

輸入格式

輸入只有一行,包含著要判斷的字串,長度在1到105之間(包含1和105),由小寫英文字母組成。

輸出格式

輸出輸入的字串是否有回文的變位詞。有的話輸出「YES」,沒有則輸出「NO」。

範例輸入1

aaabbbb

範例輸出1

YES

額外解釋1

「bbaaabb」是「aaabbbb」的變位詞,同時也符合回文格式。

範例輸入2

cdefghmnopqrstuvw

範例輸出2

NO

額外解釋2

無法找到「cdefghmnopqrstuvw」符合回文格式的變位詞。

範例輸入3

cdcdcdcdeeeef

範例輸出3

YES

額外解釋3

「ddcceefeeccdd」是「cdcdcdcdeeeef」的變位詞,同時也符合回文格式。

解題概念

這題需要知道變位詞就是一個字串中的字元之所有排列組合的可能,但在這題並不需要真的進行排列組合計算,只需要計算輸入字串的字元出現次數。因為符合回文格式的字串,其長度可能會是單數或複數。如果為複數,則所有字元的出現次數都是複數的;如果為單數,則會有一個字元的出現次數是單數。

參考答案

import java.util.Scanner;

public class Solution {

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

        final char[] s = sc.nextLine().toCharArray();
        final int[] count = new int[26];
        for (int i = 0; i < s.length; ++i) {
            final int index = s[i] - 'a';
            ++count[index];
        }
        final boolean even = s.length % 2 == 0;
        int i = 0;
        if (even) {
            for (; i < 26; ++i) {
                if (count[i] % 2 != 0) {
                    break;
                }
            }
        } else {
            boolean oneDifference = false;
            for (; i < 26; ++i) {
                if (count[i] % 2 != 0) {
                    if (oneDifference) {
                        break;
                    } else {
                        oneDifference = true;
                    }
                }
            }
        }
        System.out.println(i == 26 ? "YES" : "NO");
    }
}