Найти все комбинации палиндромных подстрок

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 

Там две петли. Внешний цикл проверяет каждую длину исходной подстроки (в порядке убывания длины), чтобы увидеть, является ли это палиндром. Если это так, он повторяется в остальной части строки и перебирает возвращаемые значения, добавляя исходную подстроку к каждому элементу, прежде чем добавлять ее к результатам.

Несколько более 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