Найти все подстроки данной строки рекурсивно в Python

Question

Данная строка "lion" должна получить следующий вывод подстрок, ["ion", "lin", "in", "io", "li", "on", "lion"]

Это то, что у меня пока есть,

def Substring(n):
   sub = [n]
   if len(n) > 2:
       sub.extend(Substring(n[1:]))
       sub.extend(Substring(n[:-1]))
   return list(sub)

мой текущий выходной сигнал ['лев', 'ион', 'вкл', 'io', 'lio', 'io', 'li']

Мне не хватает подстрок "lin" и "in", и у меня не должно быть "lio".

Я не смог понять это, если мне нужно другоеметод или если мне нужны дополнительные заявления?

Answer 1

Для этого есть однострочник, который не требует itertools.В зависимости от того, к чему вы привыкли, он может быть более или менее разборчивым.

tuple(s[i:i+j+1] for i in range(len(s)) for j in range(len(s)-i))
# ('l', 'li', 'lio', 'lion', 'i', 'io', 'ion', 'o', 'on', 'n')

Обратите внимание, что приведение tuple предназначено только для печати;без него Python предоставит вам генератор, который гораздо эффективнее, если вы выполняете итерации по нему.

Для подстрок длины 2 или больше:

tuple(s[i:i+j+1] for i in range(len(s)) for j in range(1, len(s)-i))
# ('li', 'lio', 'lion', 'io', 'ion', 'on')

Answer 2

Вот решение, которое не требует использования каких-либо специальных библиотек.
Основная идея:
Посмотрите на первый символ вашей строки.Возможная подстрока может содержать ее или пропустить.

def get_all_substrings_recursively(s):
    if len(s) == 0:
        return ['']
    # recursive call to get all substrings of s without first char
    substrings = get_all_substrings_recursively(s[1:])
    # return all substrings with and without the first char of s
    return [(s[0] + substr) for substr in substrings] + substrings

Answer 3

Вы можете использовать itertools.combinations на каждой длине возможной подстроки:

from itertools import combinations

def substring_combinations(s, min_length):
    result = []

    # Check that minimum length is valid
    if not min_length:
        return result

    # For each possible length append all substring combinations
    for i in range(min_length, len(s)+1):
        for combination in combinations(s, i):
            result.append(''.join(combination))

    return result

>>> print(substring_combinations('lion', 2))
['li', 'lo', 'ln', 'io', 'in', 'on', 'lio', 'lin', 'lon', 'ion', 'lion']

Кстати, в вашем примере, я думаю, вы пропустили некоторые допустимые параметры.
Каждый вывод в моей функции является подстрокой lion.