Дана строка s. Нужно вернуть true, если после перестановки символов в строке может получится палиндром, и false в противном случае.
Палиндром — это строка, которая читается одинаково слева направо и справа налево.
Пример 1:
Ввод: s = "cabab" Вывод: true Объяснение: можно переставить буквы и получить палиндром "abcba" или "bacab"
Пример 2:
Ввод: s = "hello" Вывод: false
Ограничения:
s содержит только английские буквы в нижнем регистре.len(s) >= 1public class Solution
{
public static bool IsPalindromePermutation(string s)
{
// слово можно сделать палиндромом при условии, что каждая буква
// встречается четное количество раз или же только 1 буква нечетное число раз
// индекс - соответствует букве (0 - 'a', 1 - 'b', ...),
// значение - 0 будет означать, что у буквы пара есть/мы не встретили букву
// значение - 1, что у буквы встретилась нечетное число раз
int[] count = new int[26];
foreach (var letter in s)
{
// ord(char) - ord('a') - позволяет перевести 'a' -> 0, 'b' -> 1 и т. д.
// подсчитываем четность с которой встречали букву
count[letter - 'a'] = (count[letter - 'a'] + 1) % 2;
}
// если 1 или 0 букв встречается нечетное число раз - значит можно сделать палиндром
return count.Count(x => x == 1) <= 1;
}
}#include <string>
#include <vector>
using namespace std;
bool isPalindromePermutation(const string& s) {
// слово можно сделать палиндромом при условии, что каждая буква
// встречается четное количество раз или же только 1 буква нечетное число раз
// индекс - соответствует букве (0 - 'a', 1 - 'b', ...)
// значение - 0 будет означать, что у буквы пара есть/мы не встретили букву
// (нам не нужно для решения задачи различать эти случаи)
// значение - 1, что у буква встретилась нечетное число раз
vector<int> count(26, 0);
for (char letter : s) {
// ord(char) - ord('a') - позволяет перевести 'a' -> 0, 'b' -> 1 и т. д.
// подсчитываем четность с которой встречали букву
count[letter - 'a'] = (count[letter - 'a'] + 1) % 2;
}
// если 1 или 0 букв встречается нечетное число раз - значит можно сделать палиндром
return accumulate(count.begin(), count.end(), 0) <= 1;
}package main;
func isPalindromePermutation(s string) bool {
// слово можно сделать палиндромом при условии, что каждая буква
// встречается четное количество раз или же только 1 буква нечетное число раз
// индекс - соответствует букве (0 - 'a', 1 - 'b', ...)
// значение - 0 будет означать, что у буквы пара есть/мы не встретили букву
// (нам не нужно для решения задачи различать эти случаи)
// значение - 1, что у буква встретилась нечетное число раз
count := make([]int, 26)
for _, char := range s {
// ord(char) - ord('a') - позволяет перевести 'a' -> 0, 'b' -> 1 и т. д.
// подсчитываем четность с которой встречали букву
count[char-'a'] = (count[char-'a'] + 1) % 2
}
// если 1 или 0 букв встречается нечетное число раз - значит можно сделать палиндром
oddCount := 0
for _, c := range count {
oddCount += c
}
return oddCount <= 1
}import java.util.*;
public class Solution {
public boolean isPalindromePermutation(String s) {
// слово можно сделать палиндромом при условии, что каждая буква
// встречается четное количество раз или же только 1 буква нечетное число раз
// индекс - соответствует букве (0 - 'a', 1 - 'b', ...)
// значение - 0 будет означать, что у буквы пара есть/мы не встретили букву
// (нам не нужно для решения задачи различать эти случаи)
// значение - 1, что у буква встретилась нечетное число раз
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
// ord(char) - ord('a') - позволяет перевести 'a' -> 0, 'b' -> 1 и т. д.
// подсчитываем четность с которой встречали букву
char ch = s.charAt(i);
count[ch - 'a'] = (count[ch - 'a'] + 1) % 2;
}
// если 1 или 0 букв встречается нечетное число раз - значит можно сделать палиндром
int oddCount = 0;
for (int c : count) {
oddCount += c;
}
return oddCount <= 1;
}
}from typing import *
def is_palindrome_permutation(s: str) -> bool:
# слово можно сделать палиндромом при условии, что каждая буква
# встречается четное кол-во раз или же только 1 буква нечетное число раз
# индекс - соответствует букве (0 - 'a', 1 - 'b', ...)
# значение - 0 будет означать, что у буквы пара есть/мы не встретили букву
# (нам не нужно для решения задачи резличать эти случаи)
# значение - 1, что у буква встретилась нечетное число раз
count = [0 for _ in range(26)]
for char in s:
# ord(char) - ord('a') - позволяет перевести 'a' -> 0, 'b' -> 1 и т д
# подсчитываем четность с которой встречали букву
count[ord(char) - ord('a')] = (count[ord(char) - ord('a')] + 1) % 2
# если 1 или 0 букв встречается нечетное число раз - значит можно сделать палиндром
return sum(count) <= 1export function isPalindromePermutation(s) {
// слово можно сделать палиндромом при условии, что каждая буква
// встречается четное кол-во раз или же только 1 буква нечетное число раз
// индекс - соответствует букве (0 - 'a', 1 - 'b', ...)
// значение - 0 будет означать, что у буквы пара есть/мы не встретили букву
// (нам не нужно для решения задачи резличать эти случаи)
// значение - 1, что у буква встретилась нечетное число раз
const count = new Array(26).fill(0);
for (const char of s) {
// char.charCodeAt(0) - 'a' - позволяет перевести 'a' -> 0, 'b' -> 1 и т д
const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
// подсчитываем четность с которой встречали букву
count[index] = (count[index] + 1) % 2;
}
// если 1 или 0 букв встречается нечетное число раз - значит можно сделать палиндром
return count.reduce((acc, val) => acc + val, 0) <= 1;
}Оценка сложности
O(n), где n - длина строки sO(1)