查找回文子字符串的所有组合

Question

如何在Python中找到一些随机输入字符串的回文子字符串的所有可能组合?例如，如果输入xxyx，应该返回的是:

[['xx', 'y', 'x'], ['x', 'xyx'], ['x', 'x', 'y', 'x']] . 

我知道如何获得所有子字符串并检查它是否为回文，但无法找到一种方法来组合成正确的解决方案，如图所示。如果问题提得不对，我很抱歉，这是我第一次提问题。

代码如下:

def find_all_subsets(seq, n):
    if n == 0:
        return [[]]
    else:
        result = []
        subsets = find_all_subsets(seq, n-1)
        for subset in subsets:
            result += [subset]
            result += [[seq[n-1]] + subset]
        return result

def check_palindrome(subsetsList):
    finalList = []
    for set in subsetsList:
        if set[::-1] == set:
            finalList.append(set)
        else:
           continue
    return finalList

if __name__ == "__main__":
    word = "xxyx"
    palindromicSubsets = check_palindrome(find_all_subsets(word, len(word)))
    print(palindromicSubsets)

Answer 1

看起来您不需要查找所有的回文子字符串，而是查找可以将输入字符串划分为回文子字符串的所有方法。(总有至少一种方法，因为单字符子字符串总是回文。)

我是这样做的:

def palindromic_substrings(s):
    if not s:
        return [[]]
    results = []
    for i in range(len(s), 0, -1):
        sub = s[:i]
        if sub == sub[::-1]:
            for rest in palindromic_substrings(s[i:]):
                results.append([sub] + rest)
    return results

有两个循环。外部循环检查初始子字符串的每个长度(按长度降序排列)，以查看它是否是回文。如果是，则对字符串的其余部分进行递归，并循环遍历返回值，将初始子字符串添加到每一项，然后将其添加到结果中。

一个更python化的方法是创建一个递归生成器:

def palindromic_substrings(s):
    if not s:
        yield []
        return
    for i in range(len(s), 0, -1):
        sub = s[:i]
        if sub == sub[::-1]:
            for rest in palindromic_substrings(s[i:]):
                yield [sub] + rest