时间戳

首页 > 解决方案 > 有没有解决递归问题的好方法？

python - 有没有解决递归问题的好方法？

问题描述

我正在尝试解决这个问题

实现一个函数substring，它接受一个字符串并返回其所有可能的子字符串。如果 (1) 是空字符串，或者 (2) 中的所有字符都以它们的相对左右顺序出现，则字符串是字符串的子字符串。我们假设原始字符串不包含任何重复字符。

例如，

>>>substring('a')
['', 'a']
>>> substring('abc')
['', 'c', 'b', 'bc', 'a', 'ac', 'ab', 'abc']

您必须使用以下代码

def substring(S):
    if S ==[]:
    else:

我最近才了解递归并尝试使用此代码。

def substring(S):
    if S ==[]:
        return ['']
    else:
        return[substring(S[1:])]+[substring(S[0])]

我该如何解决这个问题，我有什么建议可以解决这些类型的问题吗？

更新：阅读评论和答案后，我能得到的答案如下。但是，此代码的基本情况S == ''不是S == []问题所要求的。

def substring(S):
    if S =='':
        return ['']
    else:
        return substring(S[1:])+[S[0] + i for i in substring(S[1:])]

@Primusa 感谢您的建议！

标签： pythonalgorithmlist

解决方案

不确定你的任务是什么，但我不建议在这里递归。这是一个简单的代码（另见@chepner 的评论）

S = 'abc'
l = list(S)

result = []
for n in range(2**len(l)):
    result.append(''.join([l[i] for i in range(len(l)) if 2**i & n > 0]))

print(result)

推荐阅读