0

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

例子

输入：“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" ]

笔记

输入参数：只有一个参数：string s。

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

您不必担心输出数组中字符串的顺序。与 s = "aa" 一样，数组 ["a|a", "aa"] 和 ["aa", "a|a"] 都将被接受。在返回的数组 res 中的任何字符串中，字符顺序应与给定字符串中的顺序相同。（即对于 s = "ab"，您应该返回 ["a|b"] 而不是 ["b|a"]。）返回数组中的任何字符串都不应包含任何空格。例如 s = "ab" 那么 ["a|b"] 是预期的，["a |b"] or ["a| b"] or ["a | b"] 会给出错误的答案。

约束：

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
4

1 回答 1

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
于 2021-01-02T23:00:41.347 回答