查找回文子串的所有组合
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
如何找到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