#palindrome #bitset
#палиндром #набор битов
Вопрос:
Как я могу использовать битовые манипуляции в Java, чтобы проверить, является ли входная строка перестановкой палиндрома? (вместо логического массива)
Ответ №1:
Набор битов Java может помочь с битовыми манипуляциями. существует множество встроенных методов для использования с набором битов, некоторые из которых упомянуты в комментариях ниже:
private static boolean canPalindrome(String wordStr) {
BitSet bitSet = new BitSet(256);
for (int i = 0; i < wordStr.length(); i ) {
char letter = wordStr.charAt(i); // following letter ascii value
if (letter != ' ') { // space char ' ' does not affect the palindrome
bitSet.flip(letter) //flip turns 0->1 and 1->0;
}
}
int cardinality = bitSet.cardinality(); //represents all '1' bits in BitSet
return cardinality <= 1; //Palindrome can hold 0-1 chars with ODD count
}
Основная идея здесь заключается в том, чтобы отслеживать, сколько раз появляется каждая буква. возвращает значение TRUE, только если у нас есть максимум 1 буква, которая появляется нечетное количество раз в wordStr.