There's a slight ambiguity in the way you worded the question about how you'd want to handle ['a','ab','ac','add']. I'm assuming you'd want ['ab','ac','add'].
The below additionally assumes that you don't have any empty strings. That's not a good assumption.
Basically, we're building a tree out of the input values, and only keeping the leaf nodes. This is probably the most complex way to do it. I think it has the potential to be the most efficient, but I'm not certain and that's not what you asked for anyway.
from collections import defaultdict
from itertools import groupby
from typing import Collection, Dict, Generator, Iterable, List, Union
# Exploded is a recursive data type representing a culled list of strings as a tree of character-by-character common prefixes. The leaves are the non-common suffixes.
Exploded = Dict[str, Union["Exploded", str]]
def explode(subject:Iterable[str])->Exploded:
heads_to_tails = defaultdict(list)
for s in subject:
if s:
heads_to_tails[s[0]].append(s[1:])
return {
head: prune_or_follow(tails)
for (head, tails)
in heads_to_tails.items()
}
def prune_or_follow(tails: List[str]) -> Union[Exploded, str]:
if 1 < len(tails):
return explode(tails)
else: #we just assume it's not empty.
return tails[0]
def implode(tree: Exploded, prefix :Iterable[str] = ()) -> Generator[str, None, None]:
for (head, continued) in tree.items():
if isinstance(continued, str):
yield ''.join((*prefix, head, continued))
else:
yield from implode(continued, (*prefix, head))
def cull(subject: Iterable[str]) -> Collection[str]:
return list(implode(explode(subject)))
print(cull(['a','ab','ac','add']))
print(cull([ 'a boy ran' , 'green apples are worse' , 'a boy ran towards the mill' , ' this is another sentence ' , 'a boy ran towards the mill and fell']))
print(cull(['a', 'ab', 'ac', 'b', 'add']))
EDIT:
I flattened some of the calls, I hope it's easier to read and reason about this way.
It's bugging me that I can't figure out the run-time complexity of this process. I think it's O(nm) where m is the length of the overlapping prefixes, compared to O(nm log(n)) for a string comparison...
EDIT:
I started this other question in Code Review, hoping someone could help me figure out the complexity a little. Someone there pointed out that the code as written didn't actually work: groupby is a junk by any sane interpretation of its name. I've swapped out the above code, and it's a little easier to read this way as well.
EDIT:
Ok, I've imported some of the excellent suggestions for CR. At this point I'm pretty sure I'm right about the runtime complexity being better than a sort-based option.