java - 设计一个比较器来排序单词，以便每个单词的最后一个字母是下一个单词的第一个字母？

Question

好的，所以我有一个程序，其中有一部分需要“对单词进行排序，使列表中每个项目的最后一个字母是下一个项目的第一个字母，这是一种链接在一起的单词链最后和第一个字母。”

示例输入是狗、大象、长颈鹿、犀牛、老虎正确的输出是 dog,giraffe,elephant,tiger,rhinoceros而我的输出是老虎、犀牛、狗、长颈鹿、大象。

比较器是这样的:

class linkedSort implements Comparator {
    //will return 1 for a match
    //returns 0 if no match

    public int compare(Object t, Object t1) {
        char[] charArr1 = t.toString().toCharArray();
        char[] charArr2 = t1.toString().toCharArray();

        if (charArr1[charArr1.length - 1] == charArr2[0]) {
            return -1;
        } else {
            return 1;
        }
    }
}

如有任何帮助，我们将不胜感激!!

Answer 1

你不能用简单的比较器和排序来解决这个问题，因为比较没有定义 total order 。总订单是包含以下四个属性的订单:

• 反身性:x ≤ x 始终为真。
• 反对称:如果 x ≤ y 且 x ≠ y，则 y ≤ x 永远不会为真。
• 传递性:如果 x ≤ y 且 y ≤ z，则 x ≤ z
• 总数:对于任何 x 和 y，至少 x ≤ y 和 y ≤ x 之一成立。

您的订单不是全部订单。首先，它破坏了反身性:例如，“a”≤“a”。其次，它打破了反对称:“ease”≤“eve”和“eve”≤“ease”。第三，它破坏了传递性:“east”≤“tea”和“tea”≤“aver”，但“east”≤“aver”为假。最后，不全:“东”不低于“西”，“西”不低于“东”。

要解决这个问题，您需要采用不同的方法。作为提示，您可能希望将问题视为一个图形，其中字母是节点，单词是连接起始字母和结束字母的边。你能在这个图中找到一条路径，它恰好访问每条边一次吗？

希望这对您有所帮助!