HackerRank - No Prefix Set not passing all the test cases

Question

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

Answer 1

Idea with Trie is good, only you need to define custom trie for this particular problem

class Result {

    public static void noPrefix(final List<String> words) {
        final String prefix = anyElemAsPrefix(words).orElse(null);
        if (prefix != null) {
            System.out.println("BAD SET");
            System.out.println(prefix);
        } else {
            System.out.println("GOOD SET");
        }
    }

    private static Optional<String> anyElemAsPrefix(final List<String> words) {
        final PrefixCheckTrie prefixCheckTrie = new PrefixCheckTrie();
        for (final String word : words) {
            if (prefixCheckTrie.hasAnyKeyWithPrefix(word)) {
                return Optional.of(word);
            }
            prefixCheckTrie.add(word);
        }
        return Optional.empty();
    }

    private static final class PrefixCheckTrie {
        private static final int r = 256;
        private Node root;

        public boolean hasAnyKeyWithPrefix(String prefix) {
            return matchedSymbols(root, prefix, 0, new StringBuilder()).length() > 0;
        }

        private StringBuilder matchedSymbols(final Node x, final String key, final int d, final StringBuilder matchedCharacters) {
            if (x == null) return matchedCharacters;
            if (d == key.length()) return matchedCharacters;
            char c = key.charAt(d);
            if (x.next[c] == null) {
                return x.isWord ? matchedCharacters : new StringBuilder();
            }
            return matchedSymbols(x.next[c], key, d + 1, matchedCharacters.append(c));
        }

        public void add(final String key) {
            if (key == null) {
                throw new IllegalArgumentException("argument to add() is null");
            }
            root = add(root, key, 0);
        }

        private Node add(Node x, String key, int d) {
            if (x == null) x = new Node(r);
            if (d == key.length()) {
                x.isWord = true;
            } else {
                char c = key.charAt(d);
                x.next[c] = add(x.next[c], key, d + 1);
            }
            return x;
        }

        private static class Node {
            private final Node[] next;
            private boolean isWord;

            public Node(final int r) {
                this.next = new Node[r];
            }
        }
    }
}

Answer 2

Python solution here.

I essentially created a tree where each node has 10 branches for each letter a through j. I iterate through each word given character by character to construct the tree. When I am constructing a branch for a word, if I run into a node marked 'isComplete,' then I know that this word has a prefix. If I reach the end of a word and the branch I am on continues beyond, then I know this word is a prefix for another word and I return the word.

class Tree:
    def __init__(self, words):
        self.words = words
        self.root = Node(None)
        self.checkForPrefix()
        
        
    def checkForPrefix(self):
        for word in words:
            answer = self.insert(word)

            if answer is not None:
                print("BAD SET")
                print(answer)
                return
    
        print("GOOD SET")
        

    def insert(self, word):
        current = self.root
        
        for i in range(len(word)):
            c = word[i]
            
            if current.branches[self.indexOf(c)] != None and i == len(word) - 1:
                return word
            
            if current.branches[self.indexOf(c)] == None:
                current.branches[self.indexOf(c)] = Node(c)
            
            if current.branches[self.indexOf(c)].isComplete:
                return word
            
            if i == len(word) - 1:
                current.branches[self.indexOf(c)].isComplete = True
                
            current = current.branches[self.indexOf(c)]

        return None

    def indexOf(self, c):
        return ord(c) - 97
             
class Node:
    def __init__(self, value):
        self.value = value
        self.isComplete = False
        self.branches = [None] * (ord("j") - ord("a") + 1)    

def noPrefix(words):
    # Write your code here
    root = Tree(words)

Answer 3

public static void noPrefix(List<String> words) {
// here is the solution which worked for me in hackerrank. let me know if any 
// better suggestion
   HashSet<String> hashSet=new LinkedHashSet<String>();
    for (String curr : words) {
        if(hashSet.size()>1){
        for (String value : hashSet) {
          if(!curr.equalsIgnoreCase(value) 
          &&  curr.startsWith(value)){
              System.out.println("BAD SET");
              System.out.println(curr);
            return;
          }
        }
        }
        hashSet.add(curr);
    }
    System.out.println("GOOD SET");
}

Answer 4

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.

Answer 5

Make it Simple -

1. Make a sorted list from given set.
2. Iterate over this list, for each element in list just check if the next element startsWith() this element. If yes return BAD SET.
3. Return GOOD SET if step 2 never returns BAD SET.

complexity -> O(n * log n) due to sorting.