我试图解决No Prefix Set问题的HackerRank。我的解决方案是通过只有一半的测试用例。我没有得到我错过了这里。
- 问题陈述：给定N个字符串。每个字符串仅包含从
a−j（包括a−j和a−j）开始的小写字母。N个字符串的集合称为GOOD SET如果没有字符串是另一个字符串的前缀，则称为BAD SET**。
- 问题陈述：给定N个字符串。每个字符串仅包含从
- 例如：、
aab、abcde、aabcd是错误设置**，因为aab是aabcd的前缀。
- 例如：、
下面是我实现的逻辑。
class Trie {
Trie next[] = new Trie[10];
boolean end[] = new boolean[10];
}
private static void goodOrBad(String[] array, Trie start) {
for (String string : array) {
Trie current = start;
Trie previous = start;
int index = 0;
char strArray[] = string.toCharArray();
for (char c : strArray) {
index = c-'a';
if (current.end[index]) {
System.out.println("BAD SET");
System.out.println(string);
return;
}
if (current.next[index] == null) {
Trie newTrie = new Trie();
current.next[index] = newTrie;
previous = current;
current = newTrie;
}
else {
previous = current;
current = current.next[index];
}
}
previous.end[index] = true;
}
System.out.println("GOOD SET");
}- 输入：**
第一行包含N，即集合中的字符串数。
然后接下来的N行，其中第i行包含第i个字符串。
- 输出：**
如果集合有效，则输出GOOD SET。
否则，输出BAD SET，后跟条件失败的 * first string *。
- 示例：**
4
阿拉伯银行
AAC
啊
啊
- 产出：**
不良设置
啊
4条答案
按热度按时间l7wslrjt1#
问题是您只检查当前单词是否包含前一个单词作为前缀。
您还必须检查当前单词是否是Trie中已有单词的前缀。
oewdyzsn2#
让一切变得简单-
1.从给定的集合中创建一个排序列表。
1.遍历这个列表，对于列表中的每个元素，检查下一个元素是否是这个元素的
startsWith()。如果是，返回BAD SET。1.如果步骤2从未返回不良设置，则返回良好设置。
复杂度-〉O（n * log n）。
oxalkeyp3#
Python解决方案。
我实际上创建了一个树，每个节点有10个分支，分别对应字母a到j。我逐个字符地遍历每个单词来构建树。当我为一个单词构建分支时，如果我遇到一个标记为“isComplete”的节点，那么我知道这个单词有一个前缀。如果我到达了一个单词的结尾，而我所在的分支继续延伸，那么我知道这个词是另一个词的前缀，我返回这个词。
apeeds0o4#