Palindrome คืออะไร?
Palindrome คือสตริงที่เหมือนกันเมื่ออ่านจากซ้ายไปขวา หรือจากขวาไปซ้าย กล่าวอีกนัยหนึ่ง Palindrome String คือสตริงที่ Reverse แล้วเท่ากับสตริงต้นฉบับ
ตัวอย่างเช่น civic, madam เป็น Palindrome
Cat ไม่ใช่ Palindrome เนื่องจาก Reverse แล้วได้ tac ซึ่งไม่เท่ากับต้นฉบับ (cat)
เขียนโปรแกรมเพื่อตรวจสอบว่า Input String เป็น Palindrome หรือไม่
วิธีที่ 1 - หา Reverse ของสตริง
สิ่งหลักที่ต้องการในโปรแกรมคือการหา Reverse ของสตริง
Reverse สามารถหาได้ด้วยวิธีการ Reverse String ใดๆ เราจะใช้ Slicing แบบง่ายๆ เพื่อ Reverse สตริง ใช้
''.join(reversed())แบบ Built-in ก็ได้ แม้จะมีวิธีอื่น แต่นี่เป็นวิธีง่ายที่สุดเปรียบเทียบสตริงที่ Reverse กับสตริงต้นฉบับ
คืนค่า True หากทั้งสองสตริงเท่ากัน ไม่เช่นนั้นคืนค่า False
ตัวอย่าง
def isPalindrome(s):
rev=s[::-1]
if(rev==s):
return True
return False
print("Enter a string")
st=input()
print(isPalindrome(st))
ผลลัพธ์
Enter a string madam True
วิธีที่ 2 - โดยไม่ต้องหา Reverse ของสตริง
แนวคิดคือ เปรียบเทียบอักขระที่ Index แรกและสุดท้ายของสตริงต่อเนื่องจนกว่าจะไม่เท่ากัน
เราจะดู 2 ตัวอย่างโดยไม่หา Reverse −
ค่าสตริง "madam":
เปรียบเทียบอักขระแรกและสุดท้าย เท่ากัน ต่อไปเปรียบเทียบอักขระที่ 2 และ倒数 2 เท่ากันอีกครั้ง สุดท้ายเหลืออักขระเดียว ดังนั้นสตริงนี้เป็น Palindrome
ค่าสตริง "reader":
อักขระเท่ากันจนถึงการเปรียบเทียบอักขระที่ 2 และ倒数 2
เมื่อเปรียบเทียบอักขระที่ 3 และ倒数 3 ไม่เท่ากัน ดังนั้นไม่ใช่ Palindrome
เราสามารถนำแนวคิดนี้ไปใช้ผ่าน Recursion หรือ Two Pointers เราจะใช้ Two Pointers เริ่ม Pointer ซ้ายที่ 0 และ Pointer ขวาที่ Index สุดท้าย เริ่มเปรียบเทียบ หากเท่ากัน เพิ่ม Pointer ซ้าย และลด Pointer ขวา (นำไปสู่อักขระที่ 2 และ倒数 2 และต่อไป)
เมื่อไหร่คืนค่า False? หากพบว่าอักขระสำหรับชุด Pointer ใดไม่เท่ากัน เราไม่ต้องมองหา Index ต่อไป และคืนค่า False ได้เลย
เมื่อไหร่คืนค่า True? ในอีกกรณี หากสตริงเป็น Palindrome เราจะคืนค่า True เมื่อ Pointer ทั้งสองเท่ากัน (เหลืออักขระเดียวต้องตรวจสอบ) หรือ Pointer ซ้ายเกิน Pointer ขวา (ตรวจสอบอักขระทั้งหมดแล้ว) จึงคืนค่า True
ตัวอย่าง
def isPalindrome(s):
rev=s[::-1]
if(rev==s):
return True
return False
print("Enter a string")
st=input()
print(isPalindrome(st))
ผลลัพธ์
Enter a string reader False >>> Enter a string madam True
