How To Get All The Contiguous Substrings Of A String In Python?

Here is my code, but I want a better solution, how do you think about the problem?

def get_all_substrings(string):
  length = len(string)
  alist = []
  for i in xrange(length):
    for j in xrange(i,length):
      alist.append(string[i:j + 1]) 
  return alist

print get_all_substring('abcde')

Answers:

Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.

Method 1

The only improvement I could think of is, to use list comprehension like this

def get_all_substrings(input_string):
  length = len(input_string)
  return [input_string[i:j+1] for i in xrange(length) for j in xrange(i,length)]

print get_all_substrings('abcde')

The timing comparison between, yours and mine

def get_all_substrings(string):
  length = len(string)
  alist = []
  for i in xrange(length):
    for j in xrange(i,length):
      alist.append(string[i:j + 1]) 
  return alist

def get_all_substrings_1(input_string):
  length = len(input_string)
  return [input_string[i:j + 1] for i in xrange(length) for j in xrange(i,length)]

from timeit import timeit
print timeit("get_all_substrings('abcde')", "from __main__ import get_all_substrings")
# 3.33308315277
print timeit("get_all_substrings_1('abcde')", "from __main__ import get_all_substrings_1")
# 2.67816185951

Method 2

can be done concisely with itertools.combinations

from itertools import combinations

def get_all_substrings_2(string):
    length = len(string) + 1
    return [string[x:y] for x, y in combinations(range(length), r=2)]

Method 3

You could write it as a generator to save storing all the strings in memory at once if you don’t need to

def get_all_substrings(string):
    length = len(string)
    for i in xrange(length):
        for j in xrange(i + 1, length + 1):
            yield(string[i:j]) 

for i in get_all_substrings("abcde"):
    print i

you can still make a list if you really need one

alist = list(get_all_substrings("abcde"))

The function can be reduced to return a generator expression

def get_all_substrings(s):
    length = len(s)
    return (s[i: j] for i in xrange(length) for j in xrange(i + 1, length + 1))

Or of course you can change two characters to return a list if you don’t care about memory

def get_all_substrings(s):
    length = len(s)
    return [s[i: j] for i in xrange(length) for j in xrange(i + 1, length + 1)]

Method 4

I’ve never been fond of range(len(seq)), how about using enumerate and just using the index value:

def indexes(seq, start=0):
    return (i for i,_ in enumerate(seq, start=start))

def gen_all_substrings(s):
    return (s[i:j] for i in indexes(s) for j in indexes(s[i:], i+1))

def get_all_substrings(string):
    return list(gen_all_substrings(string))

print(get_all_substrings('abcde'))

Method 5

Python 3

s='abc'
list(s[i:j+1] for i in range (len(s)) for j in range(i,len(s)))

['a', 'ab', 'abc', 'b', 'bc', 'c']

Method 6

Use itertools.permutations to generate all pairs of possible start and end indexes,
and filter out only those where the start index is less than then end index. Then
use these pairs to return slices of the original string.

from itertools import permutations

def gen_all_substrings(s):
    lt = lambda pair: pair[0] < pair[1]
    index_pairs = filter(lt, permutations(range(len(s)+1), 2))
    return (s[i:j] for i,j in index_pairs)

def get_all_substrings(s):
    return list(gen_all_substrings(s))

print(get_all_substrings('abcde'))

Method 7

Another solution:

def get_all_substrings(string):
   length = len(string)+1
   return [string[x:y] for x in range(length) for y in range(length) if string[x:y]]

print get_all_substring('abcde')

Method 8

Another solution using 2-D matrix approach

p = "abc"
a = list(p)
b = list(p)
c = list(p)
count = 0
for i in range(0,len(a)):
       dump = a[i]
            for j in range(0, len(b)):
                if i < j:
                    c.append(dump+b[j])
                    dump = dump + b[j]

Method 9

If you want to get the substrings sorted by the length:

s = 'abcde'
def allSubstrings(s: str) -> List[str]:
    length = len(s)
    mylist = []
    for i in range(1, length+1):
        for j in range(length-i+1):
            mylist.append(s[j:j+i])
    return mylist

print(allSubstrings(s))

['a', 'b', 'c', 'd', 'e', 'ab', 'bc', 'cd', 'de', 'abc', 'bcd', 'cde', 'abcd', 'bcde', 'abcde']

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0