Сложность: easy
Дана строка s, вернуть true, если перестановка строки может образовать палиндром, и false в противном случае.
Пример:
Input: s = "code"
Output: false
👨💻 Алгоритм:
1⃣Вместо использования встроенной хеш-таблицы, используем массив в качестве хеш-таблицы. Для этого создаем массив длиной 128, где каждый индекс соответствует одному из 128 возможных ASCII-символов.
2⃣Проходим по строке s и записываем количество вхождений каждого символа в этот массив.
3⃣Затем определяем количество символов с нечетным числом вхождений, чтобы определить, возможна ли палиндромная перестановка строки s.
😎 Решение:
public class Solution {
public boolean canPermutePalindrome(String s) {
int[] map = new int[128];
int count = 0;
for (int i = 0; i < s.length(); i++) {
map[s.charAt(i)]++;
if (map[s.charAt(i)] % 2 == 0) {
count--;
} else {
count++;
}
}
return count <= 1;
}
}Ставь 👍 и забирай 📚 Базу знаний