I was trying to solve No Prefix Set problem on HackerRank. My Solution is passing for only half of the test-cases. I am not getting what I am missing here.
Problem Statement: Given N strings. Each string contains only lowercase letters from a−j
(both inclusive). The set of N strings is said to be GOOD SET if no string is prefix of another string else, it is BAD SET.
For example:, aab
, abcde
, aabcd
is BAD SET because aab
is prefix of aabcd
.
Here is logic I have implemented.
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");
}
Input :
First line contains N, the number of strings in the set.
Then next N lines follow, where ith line contains ith string.
Output :
Output GOOD SET if the set is valid.
Else, output BAD SET followed by the first string
for which the condition fails.
Example:
4
aab
aac
aacghgh
aabghgh
Ouput:
BAD SET
aacghgh
The problem is that you are only checking if the current word contains a previous word as a prefix.
You also have to check if the current word is a prefix of an existing word already in the Trie.