สมมติว่าเรามีสตริง เราต้องหาพาลินโดรมที่ยาวที่สุดที่สามารถสร้างได้โดยการลบหรือสับเปลี่ยนอักขระจากสตริง และถ้ามีมากกว่าหนึ่ง palindrome ให้ส่งคืนเพียงอันเดียว
ดังนั้น หากอินพุตเป็นเหมือน pqqprrs เอาต์พุตจะเป็น pqrsrqp
-
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
count :=อาร์เรย์ขนาด 256 เติม 0
-
สำหรับผมอยู่ในช่วง 0 ถึงขนาดของสตริง ทำ
-
นับ[ASCII ของ(สตริง[i]) ] :=นับ[ASCII ของ(สตริง[i]) ] + 1
-
-
เริ่มต้น :=สตริงว่าง กลาง :=สตริงว่าง สิ้นสุด :=สตริงว่าง
-
ตัวอักษร :=ASCII ของ ('a')
-
while character <=ASCII of('z') ทำ
-
ถ้า count[character] AND 1 ไม่ใช่ศูนย์ แล้ว
-
กลาง :=ตัวอักษร
-
นับ[อักขระ] :=นับ[อักขระ] - 1
-
ตัวอักษร :=ตัวอักษร - 1
-
-
มิฉะนั้น
-
สำหรับฉันอยู่ในช่วง 0 เพื่อนับ[ตัวละคร]/2 (การหารจำนวนเต็ม) ทำ
-
เริ่มต้น :=เริ่มต้น + อักขระจาก (อักขระ)
-
-
-
ตัวอักษร :=ตัวอักษร + 1
-
-
end :=เริ่มต้น
-
end :=กลับด้าน
-
return เริ่มต้นต่ออักขระจาก (กลาง) ต่อท้ายสิ้นสุด
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
