How to search for substrings of a string in a list?

Christoph Zwerschke cito at
Mon Jun 5 13:04:58 CEST 2006

Girish Sahani schrieb:
> Given a length k string,i want to search for 2 substrings (overlap
> possible) in a list consisting of length k-1 strings. These 2 substrings
> when 'united' give the original string.
> e.g given 'abc' i want to search in the list of 2-length strings
> ['ab',ac','cd','bc','bd'] to extract either
> 1) 'ab and 'ac' OR ('a' common)
> 2) 'ab' and 'bc' OR ('b' common)
> 3) 'ac' and 'bc' ('c' common)

Here is a simple brute force solution that also works for different 
lengths of your strings:

complete = 'abc'
partial = ['ab','ac','cd','bc','bd']

for i1, s1 in enumerate(partial):
     for s2 in partial[i1+1:]:
         if set(s1).union(set(s2)) == set(complete):
             print s1, s2

-- Christoph

More information about the Python-list mailing list