Keep the longest word fragment in a Python list and discard the others

user_4250010 0
Viewed 72

I have a list of string and some are fragments of a longer word. I just want to keep the longest version of each word fragment.

In the following list I would like to keep the longest word 'indoor outdoor beanbag lounger' and remove the other word fragments.

Example:

list1 = ["indoor outdoor", "indoor outdoor beanbag", "indoor outdoor beanbag lounger"]

Thoughts and things I've tried so far.

I've tried duplicating the list iterating over it and removing the first exact copy of itself. The next step would be to check if a word is found. e.g. is indoor outdoor found in indoor outdoor beanbag if True, then delete from list.

Something along those lines? I've tried looking at Polyfuzz which works to an extent, but I can't seem to fine tune it and there must be a way to solve it by looping though the list.

My code so far which iterates and removes the first exact match from list 2

list1 = ["indoor outdoor", "indoor outdoor beanbag", "indoor outdoor beanbag lounger"]
list2 = ["indoor outdoor", "indoor outdoor beanbag", "indoor outdoor beanbag lounger"]
    
for i in list1:
    cleaned_list = [x for x in list1 if x != i]

    print(cleaned_list)
python-3.x list
2 Answers

The most naive approach is to get a set of proper substrings by checking if any string is a proper substring of any other string:

substrings = {w1 for w1 in list1 for w2 in list1 if w1 in w2 and w1 != w2}

Then subtract this set from the original list. The leftovers are the longest strings:

set(list1) - substrings
#{'indoor outdoor beanbag lounger', "hello is it me you're looking for"}

You can do better by observing that a longer string cannot be a substring of a shorter one. Sort the list in the order of string length:

list2 = sorted(list1, key=len)

Organize a nested loop that searches for the substrings:

substrings = set()
for i in range(len(list2)):
    for j in range(i + 1, len(list2)):
        if list2[i] in list2[j]: 
            substrings.add(list2[i])
            break # There may be more matches, but we don't care

You will start seen performance improvements for lists with 15+ strings.

user_44929320

As suggested by @atru, if all you need is the longest entry and all your entries have words separated by whitespace, then this simple code will solve your issue:

sorted(list1, key = lambda x: len(x))[0]

The above code sorts your list by length and retrieves the shortest entry.

user_142490870
Related