在 Python 中查找已排序字符串的回文子字符串的数量

pythonserver side programmingprogramming更新于 2025/9/27 8:44:17

假设我们有一串小写字符(全部为 ASCII 字符),我们必须找到给定字符串的所有不同的连续回文子字符串。

因此,如果输入为"level",则输出将为 7,因为有七个子字符串 ['level', 'eve', 'l', 'e', 'v', 'e', 'l']。

为了解决这个问题,我们将遵循以下步骤 −

  • N := 26

  • n := str 的长度

  • sum := 0

  • my_map := 大小为 N 的列表并用 0 填充

  • 对于范围在 0 到 n 内的 i,执行

    • my_map[(str[i]) 的 ASCII - ('a') 的 ASCII ] := my_map[(str[i]) 的 ASCII - ('a') 的 ASCII ] + 1

  • 对于范围在 0 到 N 内的 i,执行

    • 如果 my_map[i] 非零,则

      • sum := sum +(my_map[i] *(my_map[i] + 1) / 2)

  • 返回 sum

示例

让我们看看下面的实现以便更好地理解 −

N = 26
def all_palindrome_substr_count(str):
   n = len (str)
   sum = 0
   my_map = [0] * N
   for i in range(n):
      my_map[ord(str[i]) - ord('a')] += 1
  for i in range(N) :
      if (my_map[i]):
         sum += (my_map[i] * (my_map[i] + 1) // 2)
   return sum
str = "level"
print (all_palindrome_substr_count(str))

输入

"level"

输出

7

相关文章


有用资源