Remove short overlapping string from list of string

user_4932296 0
Viewed 480

I have a list of strings: mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"], I need to remove shorter strings that are substring of another string in the list.

For example in the case above, output should be : ["Tom Hanks","Tom Can"].

What I have done in python:

mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
newlst = []
for x in mylist:
    noexist = True
    for j in mylist:
        if x==j:continue
        noexist = noexist and not(x in j)         
    if (noexist==True):
        newlst.append(x)
print(newlst)

The code works fine. How can I make it efficient?

list python string
4 Answers

  • If order in output does not matter (replace ',' character with a character that doesn't occur in strings of your list):

    mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
mylist.sort(key = len)
newlst = []
for i,x in enumerate(mylist):
    if x not in ','.join(mylist[i+1:]):
        newlst.append(x)

    list comprehension alternative (less readable):

    mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
mylist.sort(key = len)
newlst = [x for i,x in enumerate(mylist) if x not in ','.join(mylist[i+1:])]

    output:

    ['Tom Can', 'Tom Hanks']

  • And if you want to keep the order:

    mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
mylist_sorted = mylist.copy()
mylist_sorted.sort(key = len)
newlst = [x for i,x in enumerate(mylist_sorted) if x not in ','.join(mylist_sorted[i+1:])]
newlst = [x for x in mylist if x in newlst]

    output:

    ['Tom Hanks', 'Tom Can']
user_49759810

See this can help you. Added answer based on question sample list :

mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
newlist = []
newstring = "|".join(mylist)
for a in mylist:
    if newstring.count(a) == 1:
        print("Big string: ",a)
        newlist.append(a)
    else:
        print("Small String: ",a) 

print(newlist)

Added if else print statement how its traverse and check condition.

user_62850540

a pretty minor improvement without changing the overall algorithm is that once you find another element that contains the current element then you can break out of the inner loop since it is skipped after that.

mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
newlist = []
for elem in mylist:
    for candidate in mylist:
        if elem == candidate:
            continue
        elif elem in candidate:
            break
    else:
        newlist.append(elem)

print(newlist)
user_58272150

If your strings are always words, you can just split on the words and filter by set operations, which should be quite fast.

from collections import Counter

items = ["Hanks", "Tom Hanks","Tom","Tom Can"]
items = set(items)  # Don't want to think about uniqueness
item_words = {}  # {item: all_words}
word_counts = Counter()  # {word: item_counts}
word_lookups = {}  # {word: {all_words: {item, ...}, ...}, ...}
for item in items:
    words = frozenset(item.split())
    item_words[item] = words
    for word in words:
        word_lookups.setdefault(word, {}).setdefault(words, set()).add(item)
        word_counts[word] += 1

def is_ok(item):
    words = item_words[item]
    min_word = min(words, key=word_counts.__getitem__)
    if word_counts[min_word] == 1:
        return True  # This item has a unique word
    for all_words, others in word_lookups[min_word].items():
        if not words.issubset(all_words):
            continue  # Not all words present
        for other in others:
            if item == other:
                continue  # Don't remove yourself
            if item in other:
                return False
    return True  # No matches

final = [item for item in items if is_ok(item)]

If you want to be very fast, consider a variation on the Aho–Corasick algorithm, where you would construct patterns for all your entries, and match them against all your inputs, and discard any patterns that have more than one match. This could potentially be linear in time.

user_22844900
Related