Return string that is not a substring of other strings - is it possible in time less than O(n^2)?
<p>You are given an array of strings. you have to return only those strings that are not sub strings of other strings in the array.
Input - <code>['abc','abcd','ab','def','efgd']</code>.
Output should be - <code>'abcd'</code> and <code>'efgd'</code>
I have come up with a solution in python that has time complexity O(n^2).
Is there a possible solution that gives a lesser time complexity?
My solution:</p>

<pre><code>def sub(l,s):
  l1=l
  for i in range (len(l)):
        l1[i]=''.join(sorted(l1[i]))
  for i in l1:      
         if s in i:
              return True
  return False

def main(l):
      for i in range(len(l)):
            if sub(l[0:i-1]+l[i+1:],l[i])==False:
                  print l[i]


main(['abc','abcd','ab','def','efgd'])                  
</code></pre>

<p>Use a <code>set</code> object to keep all the substrings. This is faster but use a lot of memory, if every string is short, you can try this.</p>

<pre><code>import string
import random
from itertools import combinations

def get_substrings(w):
    return (w[s:e] for s, e in combinations(range(len(w)+1), 2))

def get_not_substrings(words):
    words = sorted(set(words), key=len, reverse=True)
    substrings = set()

    for w in words:
        if w not in substrings:
            yield w
            substrings.update(get_substrings(w))

words = ["".join(random.choice(string.ascii_lowercase) 
    for _ in range(random.randint(1, 12))) for _ in range(10000)]
res = list(get_not_substrings(words))
</code></pre>

python string python-2.7 substring