7

お互いのアナグラムである単語をどのようにリストしますか？

私が現在の仕事に応募したとき、私はこの質問をされました。

orchestraすべての元の文字を1回だけ使用して再配置できるcarthorseため、単語は互いにアナグラムになります。

4

10 に答える 10

22

すべての文字をアルファベット順に文字列に入れ（並べ替えアルゴリズム）、結果の文字列を比較します。

于 2009-02-06T20:54:56.610 に答える
10

良いことに、私たちは皆、大量のメモリを備えたクアッド コア マシンで短い単語をインプレース ソートする C# の現実に住んでいます。:-)

ただし、たまたまメモリに制約があり、元のデータに触れることができず、これらの単語に ASCII テーブルの下半分の文字が含まれていることがわかっている場合は、それぞれの文字の出現回数をカウントする別のアルゴリズムを使用できます。並べ替えの代わりに単語。

O(N) で実行したい場合や、メモリ使用量を気にしない場合は、そのアルゴリズムを選択することもできます (各 Unicode 文字のカウンターは非常に高価になる可能性があります)。

于 2009-02-06T21:30:04.607 に答える
6

各要素を並べ替え（空白を削除）、前の要素と比較します。それらがすべて同じである場合、それらはすべてアナグラムです。

于 2009-02-06T20:54:51.230 に答える
3

興味深いことに、Eric Lippert の Fabulous Adventures In Coding ブログは、2009 年 2 月 4 日のこの投稿で、まさにこの問題のバリエーションを扱っています。

于 2009-02-06T21:02:00.420 に答える
2

リスト内の単語をよく並べ替えます。

abc、bca、cab、cbaが入力の場合、ソートされたリストはabc、abc、abc、abcになります。

これで、すべてのハッシュコードが等しくなります。HashCodesを比較します。

于 2012-04-28T01:57:49.827 に答える
2

次のアルゴリズムが機能するはずです。

  1. 各単語の文字を並べ替えます。

  2. 各リスト内のソートされた文字のリストをソートします。

  3. 各リストの各要素が等しいかどうかを比較します。

于 2009-02-06T20:57:15.560 に答える
1

文字を並べ替えて比較 (文字ごと、文字列の比較など) が最初に思い浮かびます。

于 2009-02-06T20:55:42.443 に答える
0 
public static void main(String[] args) {

    String s= "abc";
    String s1="cba";



     char[] aArr = s.toLowerCase().toCharArray(); 
     char[] bArr = s1.toLowerCase().toCharArray();

  // An array to hold the number of occurrences of each character
  int[] counts = new int[26]; 

  for (int i = 0; i < aArr.length; i++){
   counts[aArr[i]-97]++;  // Increment the count of the character at respective position
   counts[bArr[i]-97]--;  // Decrement the count of the character at respective position
  }

  // If the strings are anagrams, then counts array will be full of zeros not otherwise
  for (int i = 0; i<26; i++){
   if (counts[i] != 0)
    return false;
  }
于 2015-11-19T12:21:16.017 に答える