題目描述
多斯拉其語正在計劃發動一個攻擊來竄取羅伯特國王的王位。羅伯特國王從烏鴉那得知了這場陰謀。並計劃鎖住敵人唯一能通過的那扇門。然而,要鎖住那扇門必須要有一個鑰匙,這個鑰匙是一個回文字串的變位詞。請幫助他判斷一個字串的變位詞是否為回文。
原題網址
輸入格式
輸入只有一行,包含著要判斷的字串,長度在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");
}
}