# Eliminate shorter substrings from larger one

I have a dictionary that stores a string and its frequency which looks like this

test_dict={'large blue dog':2,
'cute blue dog':2
'cute blue elephant':1
'cute blue' :3
'blue dog':4
'large blue':2}


My final list need to contain every thing except 'large blue' as it already occurs in one super string i.e 'large blue dog'. However cute blue occurs in more than one superstring i.e [cute blue dog, cute blue elephant]

here is my solution . I am keeping track of maximum length which is 3 in this case.

completed={} # a dictionary to store filtered results
super_strings=[] #
for k,v in test_dict.items():
s=' '.join(x for x in k)

# we are dealing with strings that has max length so directly add them into a list
if len(k)==sentence_max_len:
completed.update({s:v})
super_strings.append(s)
else:
# we found a shorter string
# a helper function that returns as soon as there is atleast one match
idx=index_containing_substring(super_strings, s)

if idx==-1:
# no match found
super_strings.append(s)
else:
current_string=super_strings[idx]
if completed[current_string]==v:
# same count reject it
continue
else:
self.completed.update({s:v})
super_strings.append(s)

def index_containing_substring(the_list, substring):
for i, s in enumerate(the_list):
if substring in s:
return i
return -1


This runs fine. But is there a better data structure that can implement this functionality ? I have approx 5000 of strings with different length . Can we make use of Trie?

• your examples both appear at the start of the larger strings - will that always be the case, or can you have like dog matching big dog? Will the common parts always align on word boundaries, or can you have like cu matching cute cat? Is case significant? – Oh My Goodness Mar 1 at 16:24
• No they will be at the boundaries. so for 'big dog' we would have 'big' not 'dog' also it has to be a complete match. – Rohit Mar 1 at 16:26
• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. – Mast Mar 1 at 19:27

Store them in nested dicts. 'large blue dog' + 'large blue' becomes:

trie={}
trie['large']={}
trie['large']['blue']={}
trie['large']['blue']['dog']={ '.': 1 }
...
trie['large']['blue']['.']=1


When building the trie, remember to check if the key already exists before assigning {} to it.

Every possible key has a dict as value, except the special key . which marks end of term. For each possible substring aa bb, check if trie['aa']['bb'] exists. If so, you can inspect that nested dict to see how many matches there are.

The trie-building task is a natural fit for recursion. A builder function takes an existing trie (possibly empty) and a list of words.

It inserts the first word and now trie[first_word] is also a trie.

The function then invokes itself on the subtree, with the first word removed from the list.

Eventually it will be passed an empty list of words. Then simply insert the terminator key (; in the below example) and return.

def trie_insert(trie, words):
if len(words):
word = words.pop(0)
if word not in trie:
trie[word]={}
trie_insert( trie[word], words )
else:
trie[';']=1

test_dict={
'large blue dog':2,
'cute blue dog':2,
'cute blue elephant':1,
'cute blue' :3,
'blue dog':4,
'large blue':2
}

test_trie = {}
for key in test_dict:
trie_insert( test_trie, key.split() )

import pprint
pprint.pprint( test_trie, indent=4, depth=4, width=10 )


\$ python3.7 trie.py
{   'blue': {   'dog': {   ';': 1}},
'cute': {   'blue': {   ';': 1,
'dog': {   ';': 1},
'elephant': {   ';': 1}}},
'large': {   'blue': {   ';': 1,
'dog': {   ';': 1}}}}

• Actually I also have ‘.’ as a token – Rohit Mar 1 at 17:22
• Just pick any value that isn't a possible token. – Oh My Goodness Mar 1 at 17:23