java - 字符串数组只包含字谜？

Question

我得到了一个关于字谜的练习，它看起来非常简单，我怀疑我错过了什么。我实现的解决方案是我将在稍后展示的解决方案，我想问您是否可以考虑我的解决方案的任何优化、方法更改或问题。我用 Java 实现了算法。

现在，练习。作为输入，我有一个文本，作为输出，我应该返回该文本的每一行是否是彼此的字谜。也就是说，对于输入:

A Cab Deed Huffiest Minnows Loll
A Cab Deed Huffiest Minnow Lollipop
一份出租车契约洗牌百万元
出租车契​​约洗牌百万镇

程序应该返回 True。对于输入:

A Cab Deed Huffiest Minnows Loll
A Cab Deed Huffiest Minnow Lolls 嗨
一份出租车契约洗牌百万元
出租车契​​约洗牌百万镇

输出必须为 False(当然是因为第二行)。

现在，我的想法很简单:

• 我创建了 2 个 HashMap:ref 和 cur。
• 我解析文本的第一行，填充 ref。我将只计算字母。
• 对于每一行，我将该行解析为 cur 并检查 cur.equals(ref):如果是则返回 false
• 如果我到达文本的末尾，则意味着每一行都是彼此的变位词，所以我返回 true。

然后……就这样了。我用 88000 行的输入文本尝试了它，它运行得非常快。

有什么意见吗？建议？优化？

非常感谢您的帮助。

Answer 1

另一种选择是:

1. 从字符串中去除所有你不关心的字符(标点符号、空格)
2. 小写
3. 对字符串进行排序
4. 与引用字符串比较(用 .equals )

不过我怀疑你的方法更快。

编辑:

由于@nibot 甚至不同意我的建议，而且我不是一个在没有证据的情况下来回争论的人，here's three solutions .

它们的实现都非常相似:

1. 将行转换为小写
2. 忽略非字母字符
3. ?
4. 检查 3. 的结果与第一行的结果相匹配

那个？部分是以下之一:

• 制作 HashMap字符数
• 对字符进行排序
• 制作一个 26-int 数组(最终的哈希表解决方案，但仅适用于拉丁字母表)

我用这个运行了它们:

public static void time(String name, int repetitions, Function function,
        int expectedResult) throws Exception {
    long total = 0;
    for (int i = 0; i < repetitions; i++) {
        System.gc();
        long start = System.currentTimeMillis();
        int result = function.call();
        long end = System.currentTimeMillis();
        if (result != expectedResult) {
            System.out.println("Oops, " + name + " is broken");
            return;
        }
        total += end - start;
    }
    System.out.println("Executution of " + name + " took "
            + (total / repetitions) + " ms on average");
}

我的文件与 OP 发布的文件类似，但明显更长，从末尾开始有大约 20 行的非字谜以确保所有算法都能正常工作。

我总是得到这样的结果:

Execution of testWithHashMap took 158 ms on average
Execution of testWithSorting took 76 ms on average
Execution of testWithArray took 56 ms on average

HashMap如果:

• There was a way to make a HashMap<char, int>
• 有一种方法可以在 HashMap 中指定默认值以及一种获取和递增的方法(因此只有一次查找而不是 2 次)

但是，这些不在标准库中，所以我忽略它们(就像大多数使用 Java 的程序员一样)。

这个故事的寓意是大 O 不是一切。您需要考虑开销和 n 的大小。在这种情况下，n 相当小，HashMap 的开销很重要。对于更长的线路，这可能会改变，但不幸的是，我不想弄清楚盈亏平衡点在哪里。

如果您仍然不相信我，请考虑 GCC 使用 insertion sort 在某些情况下在其 C++ 标准库中。