打印单个单词中可能的回文子串组合的总数

Question

找出单个单词中可能的子串组合总数，不重复。

例如，

'PASTA'

有这些可能的组合：

['P', 'A', 'S', 'T', 'AA', 'ASA', 'ATA']

。因此程序应该打印7。注意，

'A'

在

'PASTA'

中出现了两次，但只算一次。但

'AA'

是一个有效的回文子串。同样，

'APA'

是无效。不会考虑它，因为这样做我们是以循环方式获取输入字符串，但我只想从左到右线性迭代它。

按照逻辑，单词

'AAA'

应该打印3，因为它有以下组合：

['A', 'AA', 'AAA']

我是一名业余程序员，所以请尽可能简洁地解释。

我尝试了以下代码：

def palindrome_count() -> None:  # Total number of palindromes possible in a single word. PASTA has 7 cases
    word = input("Enter a word: ").upper()
    palindrome_list = []

    for palindrome_length in range(1, len(word) + 1):
        character_list = [i for i in word[:palindrome_length]]

        if character_list == character_list[::-1] and ''.join(character_list) not in palindrome_list:
            palindrome_list.append(''.join(character_list))

        for j in range(palindrome_length, 0, -1):
            for character in range(j, len(word[j:]) + 1):
                character_list[j - 1] = word[character]
                if character_list == character_list[::-1] and ''.join(character_list) not in palindrome_list:
                    palindrome_list.append(''.join(character_list))

    print(palindrome_list)

但它产生了以下结果：

Enter a word: PASTA
['P', 'A', 'S', 'T', 'TT', 'STS', 'ATSTA']

预期输出：

['P', 'A', 'S', 'T', 'AA', 'ASA', 'ATA']

注 1： 在互联网中，所有其他代码都会搜索字母在原始字符串中并排的回文子串。例如，在他们的代码中，

"ABA"

会产生

["A", "B", "A", "ABA"]

。但就我而言，我希望输出像

["A", "B", "AA", "ABA"]

。

注 2： 我的代码打印列表而不是列表中存在的元素计数，因为我想查看我的程序是否完美执行。

Answer 1

您可以使用

itertools

来实现此目的。

import itertools as it

word = input('input a word: ')

# use a set to exclude duplicates
results = set()

for i in range(1, len(word)+1):
    # find all permutations with `i` letters of the word
    for w in it.permutations(word, i):
        # if this is a palindrome, save it
        if w == w[::-1]:
            # join the results into a strimg
            results.add(''.join(w))
            
print(*results, sep='\n') #{'aa', 'asa', 'apa', 'a', 'p', 'ata', 's', 't'}