javadata-structurestrie

HackerRank - No Prefix Set not passing all the test cases


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


Solution

  • 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.