4

特定の (一連の) 単語のアナグラムを計算するアルゴリズムを開発しています。信じられないほど苛立たしい例外が1つありました（しゃれは意図されていません。実際にスローされる例外はありません）。効果的な「プルーニング」を利用して繰り返し回数を減らそうと試みたにもかかわらず、私のアルゴリズムはマスター リストに複製を追加しています。この場合は final static ArrayList(StringBuilder)() 型のオブジェクトです。なぜこれが起こっているのか理解できないようです。以下は私のコードです。便宜上、メソッド全体を投稿することにしました。

これは学校の課題なので、率直な答え/解決策ではなく、自分の側でガイダンス/概念上の間違いを探しています。

編集: (割り当ての期日より前に盗作の可能性を避けるために編集されたコード。)

以下に例を示します。

**input:**
pnxish
bauelqbs
coxiuqit
elbarcbs
ptos

**output:**
Now printing anagrams: 
Anagram #0: sphinx
Anagram #1: squabble
Anagram #2: squabble
Anagram #3: quixotic
Anagram #4: quixotic
Anagram #5: scrabble
Anagram #6: scrabble
Anagram #7: pots
Anagram #8: post
Anagram #9: tops
Anagram #10: opts
Anagram #11: spot
Anagram #12: stop

助けてくれてありがとう！:)

4

5 に答える 5

4

明らかなアルゴリズム (文字を交換するだけ) は少し素朴で、同一の文字を同じ文字のインスタンスとは見なしません。たとえば、「eve」のような単語がある場合、2 つの「e」は区別されます。説明のために最初の E を太字にすると、プロセスのさまざまな時点で「 e v e」や「ev e 」などの組み合わせが得られます。

どういうわけか重複を排除する必要があります。これを行う最も簡単な方法は、コンボを何らかのタイプのセット (HashSet など) に詰め込むことです。各アイテムを 1 つだけ含むことができるため、重複は効果的に破棄されます。

ああ、Strings ではなくStringBuilders を使います。あなたがそうしていることに今気づきました。 StringBuilderをオーバーライドしないequalsため、 から継承されたバージョンが残りますObject。最終結果: 2 つの StringBuildersaとbの場合、a.equals(b)の場合のみa == b。

于 2013-05-24T22:56:08.443 に答える
2

アナグラムを格納するためにセットを使用するように見えますが、StringBuilder ではなく String を使用します。

Set<String> anagrams = new HashSet<String>();

StringBuilder を使用しない理由は、次の例に示すように、hashCode を変更しても変更されないためです。

StringBuilder sb = new StringBuilder();
System.out.println(sb.hashCode());
sb.append('c');
System.out.println(sb.hashCode());

これにより、同じハッシュ コードが出力されます。つまり、StringBuilder のハッシュ コードは、そのコンテンツのコンパレータとして信頼できないということです。

于 2013-05-24T22:55:02.803 に答える
1

これは、コードで実行している問題です。リストに "squabble" の StringBuilder オブジェクトがある場合、"squabble" を再度ビルドした後、リストに "squabble" の別の StringBuilder オブジェクトが含まれているかどうかを確認すると、contains メソッドは false を返します (文字 b が原因で発生します)。 2回発生します）。

contains は、同じ文字列を表すオブジェクトがあるかどうかではなく、オブジェクトがリストにあるかどうかをチェックしています。

于 2013-05-24T23:04:45.003 に答える
0

contains() メソッドを使用して、文字列コンテンツ自体がそこにあるかどうかを確認することはできません。

List<StringBuilder> list = new ArrayList<StringBuilder>();      
StringBuilder sb = new StringBuilder("hello");
list.add(sb);
StringBuilder sb2 = new StringBuilder("hello");
System.out.println(list.contains(sb2)); 
//echos false
于 2013-05-24T23:12:21.660 に答える