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

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

Вот некоторый код: это то же самое, что верхний ответ, который описывает алгоритм.

  1 #include<iostream>
  2 #include<string>
  3 #include<vector>
  4 #include<stack>
  5 
  6 using namespace std;
  7 
  8 bool fun(string in)
  9 {
 10 int len=in.size();
 11 int myints[len ];
 12 
 13 for(int i=0; i<len; i++)
 14 {       
 15         myints[i]= in.at(i);
 16 }
 17 vector<char> input(myints, myints+len);
 18 sort(input.begin(), input.end());
 19 
 20 stack<int> ret;
 21 
 22 for(int i=0; i<len; i++)
 23 {
 24         if(!ret.empty() && ret.top()==input.at(i))
 25                 {
 26                 ret.pop();
 27                 }
 28         else{
 29         ret.push(input.at(i));
 30         }
 31 }
 32 
 33 return ret.size()<=1;
 34 
 35 }
 36 
 37 int main()
 38 {
 39 string input;
 40 cout<<"Enter word/number"<<endl;
 41 cin>>input;
 42 cout<<fun(input)<<endl;
 43 
 44 return 0;
 45 }

Answer 2

Хотя вы можете обнаружить, что данная строка "S" является кандидатом палиндрома, используя данные методы, она все еще не очень полезна. Согласно приведенным реализациям,

isAnagramOfPalindrome ("rrss") вернет true, но фактического палиндрома нет, потому что:

Палиндром - это слово, фраза, число или другая последовательность символов или элементов, значение которых может интерпретироваться одинаково в прямом или обратном направлении. (Википедия)

А Rssr или Srrs не является реальным словом или фразой, которые можно интерпретировать. То же самое с анаграммой. Ааррдд не является анаграммой радара, потому что она не поддается интерпретации.

Таким образом, данные решения должны быть дополнены эвристической проверкой входных данных, чтобы увидеть, является ли это даже словом, а затем проверкой (посредством данных реализаций), что она вообще способна на палиндром. Затем происходит эвристический поиск по собранным сегментам с помощью n / 2! перестановки для поиска, если это на самом деле палиндромы, а не мусор. Поиск только н / 2! и не п! потому что вы вычисляете все перестановки каждой повторяющейся буквы, а затем отражаете их (в дополнение к возможному добавлению единственной буквы поворота), чтобы создать все возможные палиндромы.

Я не согласен с тем, что алгоритм является слишком большим словом, потому что этот поиск может быть выполнен чисто рекурсивно или с использованием динамического программирования (в случае слов с буквами с вхождениями более 2) и не является тривиальным.

Answer 3

def is_anagram_of_palindrome(S):
    L = [ 0 for _ in range(26) ]
    a = ord('a')
    length = 0
    for s in S:
        length += 1
        i = ord(s) - a
        L[i] = abs(L[i] - 1)
    return length > 0 and sum(L) < 2 and 1 or 0