Quel est le meilleur algorithme pour savoir si une anagramme est un palindrome?

"Algorithme" serait un trop grand mot pour elle.

Vous pouvez construire un palindrome à partir du jeu de caractères donné si chaque personnage se produit dans ce même nombre de fois (avec l'exception possible d'un seul caractère).

Pour n'importe quel autre jeu, vous pouvez facilement montrer qu'aucun palindrome existe.

La preuve est simple dans les deux cas, mais laissez-moi savoir si ce n'était pas clair.

J'ai trouvé cette solution pour le Javascript.
Cette solution est basée sur la prémisse qu'une chaîne de caractères est un anagramme d'un palindrome si et seulement si un personnage apparaît un nombre impair de fois en elle.

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;
}

Algorithme:

1. Compter le nombre d'occurrence de chaque personnage.

2. Un seul personnage étrange événement est autorisé depuis un palindrome le nombre maximum de caractère, avec une occurrence étrange peut-être à '1'.

3. Tous les autres caractères doivent se produire dans un même nombre de fois.

4. Si (2) et (3) ne parviennent pas, alors la chaîne n'est pas un palindrome.

J'ai une solution élégante dans PHP posté dans cette question sur les complexités.

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']);

Il utilise intégré dans les fonctions de PHP (pourquoi pas), mais vous pouvez le faire vous-même, comme ces fonctions sont assez simples. Tout d'abord, le count_chars fonction génère un tableau (dictionnaire en python) avec tous les personnages qui apparaissent dans la chaîne, et leur nombre d'occurrences. Il peut être substitué avec une fonction personnalisée, comme ceci:

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

Puis, un array_filter avec un count fonction est appliquée à compter combien de caractères ont un nombre impair d'occurrences:

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

Et puis vous venez de demander la comparaison dans la return (expliqué dans les commentaires de la fonction d'origine).

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

Vous suffit de compter toutes les lettres et vérifier si il y a des lettres avec odd compte. Si il y a plus d'une lettre avec odd compte la chaîne de ne pas satisfaire à ces palindrome condition.

En outre, depuis une chaîne de caractères avec un même nombre de lettres ne doit pas avoir une lettre avec un nombre impair, il n'est pas nécessaire de vérifier si la longueur de la chaîne est la même ou pas. Il faudra O(n) complexité temporelle:

Voici la mise en œuvre dans 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;
}

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

Voici un peu de code: C'est la même que la réponse sommet, qui décrit l'algorithme.

  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 }