HackerRank - 无前缀集未通过所有测试用例

Question

我试图解决HackerRank 上的无前缀集问题。我的解决方案仅通过了一半的测试用例。我没有得到我在这里缺少的东西。

\n\n

问题陈述：给定 N 个字符串。每个字符串仅包含小写字母a\xe2\x88\x92j（包括两者）。如果没有字符串是另一个字符串的前缀，则N 个字符串的集合被称为GOOD SET ，否则为BAD SET。

\n\n

例如： , aab, abcde,aabcd是BAD SET，因为aab是 的前缀aabcd。

\n\n

这是我实现的逻辑。\n

\n\n

class Trie {\n  Trie next[] = new Trie[10];\n  boolean end[] = new boolean[10];\n}\n\nprivate static void goodOrBad(String[] array, Trie start) {\n  for (String string : array) {\n    Trie current = start;\n    Trie previous = start;\n    int index = 0;\n    char strArray[] = string.toCharArray();\n    for (char c : strArray) {\n      index = c-\'a\';\n      if (current.end[index]) {\n        System.out.println("BAD SET");\n        System.out.println(string);\n        return;\n      }\n      if (current.next[index] == null) {\n        Trie newTrie = new Trie();\n        current.next[index] = newTrie;\n        previous = current;\n        current = newTrie;\n      }\n      else {\n        previous = current;\n        current = current.next[index];\n      }\n    }\n    previous.end[index] = true;\n  }\n  System.out.println("GOOD SET");\n}\n

\n\n

---

\n\n

输入：
\n第一行包含 N，即集合中字符串的数量。
\n接下来是 N 行，其中第 i 行包含第 i 个字符串。

\n\n

输出：
\n如果设置有效，则输出GOOD SET 。
\n否则，输出BAD SET，后跟first string条件失败的 。

\n\n

示例：
\n4
\naab
\naac
\naacghgh
\naabghgh

\n\n

输出：
\nBAD SET
\naacghgh

\n

Answer 1

问题是您只是检查当前单词是否包含前一个单词作为前缀。

您还必须检查当前单词是否是 Trie 中已有单词的前缀。