アナグラムがパリンドロームかどうかを調べる最良のアルゴリズムは何ですか？

Question

この問題では、小文字の英字（a〜z）の文字列のみを考慮します。

文字列は、左から右に右から左に横断したときに完全に同じ文字列を持つ場合には、パリンドロームです。例えば、以下の文字列が回文である：それは正確で構成されている場合

"のカヤック"

"codilitytilidoc"

"はneveroddoreven"

文字列Aは文字列Bのアナグラムであります同じ文字ですが、おそらく別の順序です。たとえば、次の文字列は、互いのアナグラムは以下のとおりです。

A = "メアリー" B = "軍隊" A = "rocketboys" B = "遠い空の向こうに" A = "codility" B = "codility"

書き込み関数

int isAnagramOfPalindrome（String S）;

文字列sがいくつかの回文のアナグラムである場合は1を返し、それ以外の場合は0を返します。

例えば、引数が "dooernedeevrvn"の場合、関数は回文型 "neveroddoreven"のアナグラムであるため、1を返さなければなりません。引数 "aabcba"の場合、関数は0を返します。

Answer 1

'アルゴリズム'はあまりにも大きい単語です。

各文字が偶数回（1文字を除いて）設定されている場合は、指定された文字セットから回文を構成できます。
他のセットについては、パリンドロームが存在しないことを簡単に示すことができます。

証明はどちらの場合でも簡単ですが、わからない場合は教えてください。

Answer 2

回文では、文字の反対側には、それ自身の双子の役割を果たす中間文字の場合を除いて、すべての文字が自身のコピー「双子」を持たなければなりません。

アルゴリズムでは、小文字ごとに1つずつ、長さ26の配列を作成し、文字列の文字の数をカウントして、配列のnのインデックスnに配置します。次に、配列を通過し、奇数の文字数を数えます（1文字には双子がないため）。この数字が0または1の場合、その1つの奇数文字を中央に置き、簡単に回文を生成します。そうでなければ、それを生成することは不可能です。なぜなら、双子のない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 

Answer 4

与えられた文字列 "S"が与えられたテクニックを使って候補の回文体であることを検出することはできますが、依然としてそれほど有用ではありません。所与の実装形態によれば、

isAnagramOfPalindrome（「RRSS」）がtrueを返すだろうが、実際のパリンドロームは存在しないため：パリンドロームは、単語、語句、数字、または記号または要素の他の配列である

、その意味は順方向または逆方向のどちらでも同じように解釈することができる。（Wikipedia）

RssrまたはSrrsは、解釈可能な実際の語句ではありません。アナグラムと同じです。 Aarrddは解釈できないので、レーダーのアナグラムではありません。

したがって、解決策は入力に対してヒューリスティックなチェックを加えて、それが単語であるかどうかを確認し、次に検証（実装によって）が回文可能であることを確認する必要があります。それから、n/2の収集されたバケットを使った経験則的な検索があります。それらが実際にパリンドロームであり、ゴミでないかどうかを検索する順列。検索はn/2だけです！ nではなく！繰り返される文字のすべての順列を計算してから、これらの文字をミラーリングして（おそらく単数のピボット文字を追加して）、すべての可能な回文を作成するからです。

この検索は純粋に再帰的に行うこともダイナミックプログラミング（2より大きい出現を伴う単語の場合）を使用することもでき、それほど重要ではないので、アルゴリズムはあまりにも大きい単語には同意しません。

Answer 5

私はJavascriptのこの解決策を考え出しました。 この解決策は、最大で1文字が奇数回である場合にのみ、文字列が回文のアナグラムであることを前提としています。

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

私はこのコードを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 7

ここにいくつかのコードがあります：これは、アルゴリズムを説明するトップアンサーと同じです。

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 8

アルゴリズム：

1. 各文字の出現回数をカウントします。

2. 回文では、奇数オカレンスの最大文字数は '1'にな​​ることができるので、奇数オカレンスでは1文字のみが許可されます。

3. 他のすべての文字は偶数回発生します。

4. （2）と（3）が失敗した場合、指定された文字列は回文ではありません。

Answer 9

これは、他の回答に追加されています。私たちは見た文字の数を把握したいと思っています。手紙に複数の奇数がある場合、回文を形成することはできません。奇数のカウントは中央に行くが、奇数のカウントは1つしかできない。

ハッシュマップを使用してカウントを記録できます。ハッシュマップの検索は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") 

Answer 10

私はPHPでのきちんとした解決策は、複雑についてthis questionに掲載さがあります。ここでは、それがコードしているのです。

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で辞書）を生成します。あなたはちょうどその

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

そして：count機能付きarray_filterが発生奇数を持っているどのように多くの文字カウントするように適用され、その後

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

：それは、このようなカスタム関数で置換することができますreturn（元の機能のコメントに説明があります）に比較を適用します。

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

Answer 11

これはO（n）で実行されます。 1つ以外のすべての文字については、偶数でなければなりません。オプションの奇数文字は任意の奇数にすることができます。

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 12

は、あなただけのすべての文字をカウントし、奇数カウント付きの文字があるかどうかを確認する必要があります。奇数カウントの文字が複数ある場合、文字列は上記のパリンドローム条件を満たしません。
さらに、偶数文字の文字列に奇数の文字が含まれてはならないため、文字列の長さが偶数であるかどうかを確認する必要はありません。それはしばらくしているが、私は就職の面接Iでこのような質問をしたとして - すべての権利

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 13

：ここjavascriptでの実装です

：それは、O（n）の時間計算がかかりますPythonのいくつかの行で試してみる必要がありました。基本的な考え方は、偶数の文字のための回文であるアナグラムがある場合、各文字は2回（または2n回のようなもの、すなわちカウント％2 == 0）発生するということです。さらに、奇数の文字については、1文字（中央の文字）が1回だけ（または不均等数 - ％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)