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')
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
range is quicker than xrange for such a small range
range :(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)]
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)]
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'))
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']
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'))
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')
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]
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']
