查找回文子串的所有组合

Find all combinations of palindromic substrings

如何找到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)

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

这是我完成的方法:

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

有两个循环。外层循环检查初始子串的每个长度(按长度降序)看它是否是回文。如果是这样,它将递归字符串的其余部分并遍历返回的值,在将其添加到结果之前将初始子字符串添加到每个项目。

一种稍微更像 Pythonic 的方法是制作一个递归生成器:

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