在 Python 中查找通过从字符串中删除或打乱字符而形成的最长回文

pythonserver side programmingprogramming更新于 2025/10/10 14:04:17

假设我们有一个字符串;我们必须找到通过从字符串中删除或打乱字符而生成的最长回文。如果有多个回文,则仅返回一个。

因此,如果输入类似于 pqqprrs,则输出将是 pqrsrqp。

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

  • count := 大小为 256 的数组,用 0 填充

  • 对于范围为 0 到字符串大小的 i,执行

    • count[ASCII of(string[i]) ] := count[ASCII of(string[i]) ] + 1

  • begin := 空白字符串,mid := 空白字符串,end := 空白字符串

  • character := ASCII of('a')

  • 当 character <= ASCII of('z') 时,执行

    • 如果 count[character] AND 1 非零,则

      • mid := character

      • count[character] := count[character] - 1

      • character := character - 1

    • 否则,

      • 对于范围从 0 到 count[character]/2 的 i(整数除法),执行

        • begin := begin + character from (字符)

    • character := character + 1

  • end := begin

  • end := reverse end

  • 返回开始连接字符从(中间)连接结束

示例

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

def get_palindrome(string):
   count = [0]*256
   for i in range(len(string)):
      count[ord(string[i])] += 1
   begin = ""
   mid = ""
   end = ""
   character = ord('a')
   while character <= ord('z'):
      if (count[character] & 1):
         mid = character
         count[character] -= 1
         character -= 1
      else:
         for i in range(count[character]//2):
            begin += chr(character)
      character += 1
   end = begin
   end = end[::-1]
   return begin + chr(mid) + end
string = "pqqprrs"
print(get_palindrome(string))

输入

"pqqprrs"

输出

pqrsrqp

相关文章


有用资源