查找字符串的回文分解

Question

我正在尝试解决字符串的回文分解问题。我想用递归来解决它。以下是部分条件。

示例

输入：“abracadabra”

输出：[ "a|b|r|a|c|a|d|a|b|r|a", "a|b|r|a|c|ada|b|r|a ", "a|b|r|aca|d|a|b|r|a"]

备注

输入参数：参数只有一个：字符串s。

输出：Return 字符串 res 数组，包含给定字符串的所有可能的回文分解。要分隔分解字符串中的子字符串，请使用“|”作为它们之间的分隔符。

约束条件：

1 <= |s| <= 20 s 只包含小写字母 ('a' - 'z').

任何字符串都是它自己的子字符串。

这是 python 代码。你能提供一个更简单的策略来解决这个问题吗？我还需要书籍清单、学习算法实现的链接 python 来解决这类问题以及动态规划。

def isPalindrome(X, i, j):
 
    while i <= j:
        if X[i] != X[j]:
            return False
        i = i + 1
        j = j - 1
 
    return True
 
# Recursive function to find the minimum cuts needed in a String
# such that each partition is a palindrome
def minPalinPartition(X, i, j):
 
    # base case: if starting index i and ending index j are equal
    # or X[i..j] is already a palindrome.
    if i == j or isPalindrome(X, i, j):
        return 0
 
    # stores minimum number cuts needed to partition X[i..j]
    min = float('inf')
 
    # take the minimum over each possible position at which the
    # can be cut
 
    """
        (X[i]) | (X[i+1..j])
        (X[i..i+1]) | (X[i+2..j])
        (X[i..i+2]) | (X[i+3..j])
        ...
        ...
        (X[i..j-1]) | (X[j])
    """
 
    for k in range(i, j):
 
        # recur to get minimum cuts required in X[i..k] and X[k+1..j]
        count = 1 + minPalinPartition(X, i, k) + minPalinPartition(X, k + 1, j)
 
        if count < min:
            min = count
 
    # return the minimum cuts required
    return min

Answer 1

你可以把它当作一个生成器，像这样：

def palinBreak(S):
    if len(S) == 1: yield S; return
    for n in range(1,len(S)+1):
        if S[:n] != S[:n][::-1]: continue
        yield from (S[:n]+"|"+pb for pb in palinBreak(S[n:]))


for pb in palinBreak("abracadabra"): print(pb)

a|b|r|a|c|a|d|a|b|r|a
a|b|r|a|c|ada|b|r|a
a|b|r|aca|d|a|b|r|a

查找字符串的回文分解

Finding palindromic decomposition of a String

python

algorithm

recursion

palindrome