Каков наилучший алгоритм, чтобы определить, является ли анаграмма палиндромом?

Question

В этой задаче мы рассматриваем только строки строчных букв английского алфавита (az).

Строка является палиндромом, если она имеет точно такую ​​же последовательность символов при прохождении слева направо, как право-налево.Например, следующие строки являются палиндромами:

"каяк"

"codilitytilidoc"

"neveroddoreven"

Строка A является анаграммойстрока B, если она состоит из точно таких же символов, но, возможно, в другом порядке.Например, следующие строки являются анаграммами друг друга:

A = "mary" B = "армия" A = "rocketboys" B = "octobersky" A = "codility" B = "codility"

Напишите функцию

int isAnagramOfPalindrome (String S);

, которая возвращает 1, если строка s является анаграммой какого-либо палиндрома, или возвращает 0 в противном случае.

Например, ваша функция должна возвращать 1 для аргумента "dooernedeevrvn", потому что это анаграмма палиндрома "neveroddoreven".Для аргумента "aabcba" ваша функция должна вернуть 0.

Answer 1

«Алгоритм» был бы слишком большим словом для него.

Вы можете построить палиндром из заданного набора символов, если каждый символ встречается в этом наборе четное число раз (с возможным исключением одного символа).
Для любого другого набора вы можете легко показать, что палиндрома не существует.

Доказательство простое в обоих случаях, но дайте мне знать, если это не ясно.

Answer 2

В палиндроме у каждого персонажа должна быть своя копия, "двойник", на другой стороне строки, за исключением случая средней буквы, которая может выступать в качестве своего собственного близнеца.

Алгоритм, который вы ищете, будет создавать массив длиной 26, по одному для каждой строчной буквы, и начинать считать символы в строке, помещая количество символов n в индекс n массива. Затем он пройдет через массив и посчитает количество символов с нечетным количеством (потому что в одной букве нет двойника). Если это число 0 или 1, поместите эту нечетную букву в центр, и палиндром будет легко сгенерирован. Иначе, невозможно сгенерировать одно, потому что существуют две или более буквы без двойников, и они не могут быть оба в центре.

Answer 3

Алгоритм:

1. Подсчет количества вхождений каждого символа.

2. Допускается только один символ с нечетным вхождением, поскольку в палиндромемаксимальное количество символов с нечетным вхождением может быть «1».

3. Все остальные символы должны встречаться четное число раз.

4. Если (2) и (3) не пройдены, то данная строкаэто не палиндром.

Answer 4

я написал этот код в Java.я не думаю, что это будет хорошим ^^,

 public static int isAnagramOfPalindrome(String str){
     ArrayList<Character> a = new ArrayList<Character>();

     for(int i = 0; i < str.length(); i++){
         if(a.contains(str.charAt(i))){
             a.remove((Object)str.charAt(i));
         }
         else{
             a.add(str.charAt(i));
         }
     }
     if(a.size() > 1)
        return 0;
     return 1;
 }

Answer 5

Я придумал это решение для Javascript.Это решение основано на предпосылке, что строка является анаграммой палиндрома, если и только если не более одного символа встречается в ней нечетное число раз.

function solution(S) {
    var retval = 0;
    var sorted = S.split('').sort(); // sort the input characters and store in 
                                     // a char array
    var array = new Array();

    for (var i = 0; i < sorted.length; i++) {

        // check if the 2 chars are the same, if so copy the 2 chars to the new
        // array
        // and additionally increment the counter to account for the second char
        // position in the loop.
        if ((sorted[i] === sorted[i + 1]) && (sorted[i + 1] != undefined)) {
            array.push.apply(array, sorted.slice(i, i + 2));
            i = i + 1;
        }
    }

    // if the original string array's length is 1 or more than the length of the
    // new array's length
    if (sorted.length <= array.length + 1) {
        retval = 1;
    }

    //console.log("new array-> " + array);
    //console.log("sorted array-> " + sorted);
    return retval;
}

Answer 6

Хорошо - это было давно, но, поскольку мне задали такой вопрос на собеседовании, мне нужно было попробовать его в нескольких строках Python.Основная идея состоит в том, что если есть анаграмма, которая является палиндромом для четного числа букв, то каждый символ встречается дважды (или что-то вроде 2n раз, то есть count% 2 == 0).Кроме того, для нечетного числа символов один символ (тот, что посередине) может встречаться только один раз (или нечетное число - считать% 2 == 1).Я использовал набор в python, чтобы получить уникальные символы, а затем просто считать и прерывать цикл, когда условие не может быть выполнено.Пример кода (Python3):

def is_palindrome(s):
  letters = set(s)
  oddc=0
  fail=False

  for c in letters:
      if s.count(c)%2==1:
          oddc = oddc+1

      if oddc>0 and len(s)%2==0:
          fail=True
          break
      elif oddc>1:
          fail=True
          break

  return(not fail)

Answer 7

Вы просто должны посчитать все буквы и проверить, есть ли буквы с нечетным числом.Если существует более одной буквы с нечетным числом, строка не удовлетворяет вышеуказанному условию палиндрома.
Кроме того, поскольку строка с четными цифрами не должна иметь буквы с нечетным числом, нет необходимости проверять, является ли строкадлина четная или нет.Это займет O (n) сложность времени:

Вот реализация в javascript:

function canRearrangeToPalindrome(str)
{
    var letterCounts = {};
    var letter;
    var palindromeSum = 0;
    for (var i = 0; i < str.length; i++) {
        letter = str[i];
        letterCounts[letter] = letterCounts[letter] || 0;
        letterCounts[letter]++;
    }
    for (var letterCount in letterCounts) {
        palindromeSum += letterCounts[letterCount] % 2;
    }

    return palindromeSum < 2;
}

Answer 8

Это работает в O (n). Для всех символов, кроме одного, должно быть четным. дополнительный нечетный символ может быть любым нечетным числом.

например. abababa

def anagram_of_pali(str):
    char_list = list(str)
    map = {}
    nb_of_odds = 0

    for char in char_list:
        if char in map:
            map[char] += 1
        else:
            map[char] = 1

    for char in map:
        if map[char] % 2 != 0:
            nb_of_odds += 1

    return True if nb_of_odds <= 1 else False

Answer 9

У меня есть аккуратное решение в PHP, опубликованное в этот вопрос о сложностях.

class Solution { 

    // Function to determine if the input string can make a palindrome by rearranging it
    static public function isAnagramOfPalindrome($S) {

        // here I am counting how many characters have odd number of occurrences
        $odds = count(array_filter(count_chars($S, 1), function($var) {
            return($var & 1);
        }));
        // If the string length is odd, then a palindrome would have 1 character with odd number occurrences
        // If the string length is even, all characters should have even number of occurrences
        return (int)($odds == (strlen($S) & 1));
    }
}

echo Solution :: isAnagramOfPalindrome($_POST['input']);

Он использует встроенные функции PHP (почему бы и нет), но вы можете сделать это самостоятельно, так как эти функции довольно просты.Во-первых, функция count_chars генерирует именованный массив (словарь в python) со всеми символами, которые появляются в строке, и их количеством вхождений.Его можно заменить пользовательской функцией, такой как:

$count_chars = array();
foreach($S as $char) {
    if array_key_exists($char, $count_chars) {
        $count_chars[$char]++;
    else {
        $count_chars[$char] = 1;
    }
}

Затем применяется array_filter с функцией count для подсчета количества символов с нечетным числом вхождений:

$odds = 0;
foreach($count_chars as $char) {
    $odds += $char % 2;
}

И тогда вы просто применяете сравнение в return (объяснено в комментариях к исходной функции).

return ($odds == strlen($char) % 2)

Answer 10

Это добавляет к другим данным ответам. Мы хотим отслеживать количество каждой увиденной буквы. Если у нас будет более одного нечетного числа для письма, мы не сможем сформировать палиндром. Нечетное число будет посередине, но только одно нечетное число может сделать это.

Мы можем использовать хэш-карту для отслеживания количества. Поиск для hashmap - O (1), поэтому он быстрый. Мы можем запустить весь алгоритм в O (n). Вот это в коде:

if __name__ == '__main__':
    line = input()

    dic = {}
    for i in range(len(line)):
        ch = line[i]
        if ch in dic:
            dic[ch] += 1
        else:
            dic[ch] = 1

    chars_whose_count_is_odd = 0
    for key, value in dic.items():
        if value % 2 == 1:
            chars_whose_count_is_odd += 1

    if chars_whose_count_is_odd > 1:
        print ("NO")
    else:
        print ("YES")