Python中查詢透過移除或改組字元生成的字串的最長迴文子串

假設我們有一個字串；我們必須找到可以透過刪除或改組字串中的字元生成的**最長**迴文。如果存在多個迴文，則只返回一個。

因此，如果輸入類似於pqqprrs，則輸出將是pqrsrqp。

  • 為了解決這個問題，我們將遵循以下步驟：

  • count := 大小為256的陣列，填充為0

  • 對於 i 從0到字串大小，執行：

    • count[string[i]的ASCII碼] := count[string[i]的ASCII碼] + 1

  • begin := 空字串，mid := 空字串，end := 空字串

  • character := 'a'的ASCII碼

  • 當character <= 'z'的ASCII碼時，執行：

    • 如果 count[character] AND 1 非零，則

      • mid := character

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

      • character := character - 1

    • 否則，

      • 對於 i 從0到 count[character]/2（整數除法），執行：

        • begin := begin + character (來自character)

    • character := character + 1

  • end := begin

  • end := 反轉end

  • 返回 begin + mid + 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

更新於：2020年8月25日

228 次瀏覽

啟動您的職業生涯

完成課程後獲得認證

開始
廣告