4

我一直在开发一种算法来计算给定（一组）单词的字谜。我刚刚让它工作，有一个令人难以置信的令人沮丧的异常（没有双关语；没有抛出实际的异常）。尽管我尝试利用有效的“修剪”来减少重复次数，但我的算法正在将重复项添加到主列表中，在本例中是最终静态 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”这样的词，两个“e”是不同的；如果我们将第一个 E 加粗以进行说明，您会在过程中的各个点得到像“ e v e”和“ev e ”这样的组合。

您需要以某种方式消除重复项。最简单的方法是将组合填充到某种类型的 Set 中（如 HashSet）。它只能包含每个项目之一，因此将有效地丢弃重复项。

哦，使用Strings，而不是StringBuilders。我刚刚注意到你正在这样做。 StringBuilder不会覆盖equals，因此您留下的版本继承自Object. 最终结果：对于两个 StringBuildera和b，a.equals(b)仅当a == b.

于 2013-05-24T22:56:08.443 回答
3

一个简单的解决方案是使用 aSet来存储你的字谜。这将处理重复的值。

我的猜测是您使用的是列表，因为您的变量名为anagramList. 您可以在这里找到 JavaDoc ：http Set: //docs.oracle.com/javase/6/docs/api/java/util/Set.html

于 2013-05-24T22:51:37.670 回答
2

我希望使用 Set 来存储字谜，但使用 String 而不是 StringBuilder，即

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

这是您在代码中遇到的问题。如果您的列表中有一个 StringBuilder 对象用于“squabble”，当您再次构建“squabble”后检查列表是否包含“squabble”的不同 StringBuilder 对象时，contains 方法将返回 false（这是因为字母 b发生两次）。

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 回答