I'm in doubt here. Following the problem description and samples explanations, actual test case 1 should print BAD SET with the third string "edchgb", but the test case expect an output of "d" which is evaluated later. Also, "d" is the prefix, not the string that contains it. Can someone explain me this?

my Python 3 attempt by incrementally inserting words into a trie (thanks to inspiration from many of you guys) (must be some other "cleaner" way to do the create dict if not exists step, but I prefer readability in my own terms XD):

def noPrefix(words):
    # Write your code here
    _end = "_end"
    trie = {}
    
    # return the current word where the check fails
    def bad(s):
        print("BAD SET")
        print(s)
    
    # incremental insertion of words
    for word in words:
        current = trie
        # insert per letter
        for c in word:
            # FAIL: a processed word is the prefix of the current word
            if _end in current:
                bad(word)
                return
						
            # create dict if missing
            if c not in current:
                current[c] = {}
            current = current[c]
        
        # FAIL: the current word is a prefix of a processed word
        if any(key != _end for key in current):
            bad(word)
            return
        
        # FAIL: current word has already been inserted
        # duplicate words counted as self - prefix
        if _end in current:
            bad(word)
            return
        
        # mark the current node where a word ends here
        current[_end] = _end
    print("GOOD SET")

I'd love to hear some opinions on my solution.

def noPrefix(words): word_dict = dict()

for i, word in enumerate(words):
    if word in word_dict:
        word_dict[word].append(i)
    else:
        word_dict[word] = [i]

bad_ind = float('inf')
for i, word in enumerate(words):
    if i == bad_ind:
        break

    # Check substrings
    for j in range(len(word)-1):
        if word[0:j+1] in word_dict:
            bad_ind = min( bad_ind, max(i, word_dict[word[0:j+1]][0]) )

    # Check if full string repeats
    if len(word_dict[word]) > 1:
        bad_ind = min(bad_ind, word_dict[word][1])

if bad_ind == float('inf'):
    print("GOOD SET")
else:
    print("BAD SET")
    print(words[bad_ind])

return

Tried using .sort() such that the solution boils down to comparing neighbouring words. Unfortunately this violates the "tested first" condition due to the reordering of words:

def noPrefix_fail(words: list) -> None:
    words.sort()    # sort leixcographically
    for w1, w2 in zip(words, words[1:]): # sliding window of word pairs
        if w2.startswith(w1):
            print("BAD SET")
            print(w1)   # incorrect due to .sort()
            return
    print("GOOD SET")

The test cases are bad. They are bad because author is making an assumption on which data structure the developer is going to use. If you try to brute force the problem then you might be left scratching your head as to why it is not working. But if you use a Trie then the test cases make sense.

For example on test case 1:

If you use brute force you will check first if aab is a prefix of any other words in the list. This means that you will test aabghgh first and that is what you will print.

If you use a Trie tree, then you will first start building the tree with aab, next you will modify the tree with aac, then you will begin to modify the tree with aacghgh. At this point you will find that aacghgh does have a prefix, and it will get printed, thus passing the test case.

Test cases should be written in a way that are agnostic of the algorithm that the developer uses to solve it. There are always so many ways to solve the same problem. If the test cases are not agnostic then it should be clear to the developer what algorithm should be used up front.