查找字符串的回文分解
Finding palindromic decomposition of a String
我正在尝试解决字符串的回文分解问题。我想用递归来解决它。以下是部分条件。
示例
输入:“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 数组,包含给定字符串的所有可能的回文分解。要分隔分解字符串中的子字符串,请使用“|”作为它们之间的分隔符。
您无需担心输出数组中字符串的顺序。与 s = "aa" 一样,数组 ["a|a", "aa"] 和 ["aa", "a|a"] 都将被接受。
在 returned 数组 res 中的任何字符串中,字符顺序应与给定字符串中的顺序保持一致。 (即对于 s = "ab" 你应该 return ["a|b"] 而不是 ["b|a"]。)
returned 数组中的任何字符串都不应包含任何空格。例如s = "ab" 那么 ["a|b"] 是预期的,["a |b"] 或 ["a| b"] 或 ["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
你可以把它当作一个生成器,像这样:
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
我正在尝试解决字符串的回文分解问题。我想用递归来解决它。以下是部分条件。
示例
输入:“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 数组,包含给定字符串的所有可能的回文分解。要分隔分解字符串中的子字符串,请使用“|”作为它们之间的分隔符。
您无需担心输出数组中字符串的顺序。与 s = "aa" 一样,数组 ["a|a", "aa"] 和 ["aa", "a|a"] 都将被接受。 在 returned 数组 res 中的任何字符串中,字符顺序应与给定字符串中的顺序保持一致。 (即对于 s = "ab" 你应该 return ["a|b"] 而不是 ["b|a"]。) returned 数组中的任何字符串都不应包含任何空格。例如s = "ab" 那么 ["a|b"] 是预期的,["a |b"] 或 ["a| b"] 或 ["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
你可以把它当作一个生成器,像这样:
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