Найти точки уникальности строк в списке

Question

Точка уникальности (UP) определяется как точка слова, в которой слово больше не соответствует началу других слов. Например, представьте лексикон, состоящий только из слов lexicon = ['cat', 'cats', 'catsuit']. В этом случае слова cat и cats не будут иметь UP, а UP catsuit будет catsu.

Чтобы определить UP слов лексикона, я ' мы написали код python. Тем не менее, это очень неэффективно, и поэтому я хотел бы выложить его в открытую. Может быть, вы можете улучшить это, сделать это быстрее. Слова хранятся в переменной lexicon.

# set up list to carry UPs
ups = []

# set up lexicon with candidates for comparison
testlexicon = list(lexicon)

# compare every word with other words in testlexicon
for word in lexicon:

    # remove word from textlexicon so that it is not compared with itself
    testlexicon.remove(word)

    # haven't found any UP yet
    up_found = False

        # incrementally compare first chars until unique
        for char in range(len(word)):
            char += 1

            # construct onset up to char x
            onset = word[:char]

            # construct regular expression
            my_regex = r"\b" + re.escape(onset) + r"*"
            r = re.compile(my_regex)

            # search for words with same onset
            targets = filter(r.match, testlexicon)

            # if not other words share onset, UP is found
            if not targets:
                ups.append(onset)
                up_found = True
                break    

        # if no UP found, mark word
        if up_found == False:
            ups.append('has no UP')

        # add word again to test lexicon
        testlexicon.append(word)

Я думаю, что может быть быстрее построить лексическое дерево, которое будет иметь столько же root узлов, сколько букв алфавита и узел для каждого символа. Каждое слово может быть представлено как путь в дереве, в результате чего листья, которые будут нести только одно слово, представляют UP. В моем случае я хотел бы построить новую лексику со словами в первом столбце и их UP (или 'has no UP') во втором столбце. Есть ли у вас какие-либо предложения?