พาลินโดรมคืออะไร
palindrome เป็นสตริงที่เหมือนกันเมื่ออ่านจากซ้ายไปขวาหรือจากขวาไปซ้าย กล่าวอีกนัยหนึ่ง สตริงพาลินโดรมคือสตริงที่กลับด้านเท่ากับสตริงเดิม
ตัวอย่างเช่น พลเมือง มาดามเป็นพาลินโดรม
แมวไม่ใช่พาลินโดรม เนื่องจากกลับเป็น tac ซึ่งไม่เท่ากับสตริงเดิม (cat)
เขียนโปรแกรมเพื่อค้นหาว่าสตริงอินพุตเป็นพาลินโดรมหรือไม่
วิธีที่ 1 - ค้นหาการย้อนกลับของสตริง
-
สิ่งสำคัญในโปรแกรมคือการหาส่วนกลับของสตริง
-
การย้อนกลับสามารถพบได้โดยใช้วิธีการใดๆ ในการย้อนกลับสตริง เราจะใช้วิธีการแบ่งส่วนอย่างง่ายเพื่อย้อนกลับสตริง สามารถใช้ inbuilt ''.join(reversed()) ได้ แม้ว่าจะมีวิธีอื่นๆ ในการย้อนกลับสตริง แต่เราจะใช้วิธีง่ายๆ แทน
-
เปรียบเทียบสตริงที่กลับด้านกับสตริงเดิม
-
คืนค่า จริง หากทั้งสองสตริงเท่ากัน มิฉะนั้น คืนค่า เท็จ
ตัวอย่าง
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 - ไม่พบส่วนกลับของสตริง
แนวคิดคือการเปรียบเทียบอักขระอย่างต่อเนื่องในดัชนีแรกและดัชนีสุดท้ายของสตริงจนกว่าจะไม่เท่ากัน
เราจะเห็นตัวอย่างสองตัวอย่างโดยไม่พบส่วนกลับของสตริง −
ค่าสตริง "มาดาม":
-
เราเปรียบเทียบอักขระตัวแรกและตัวสุดท้ายที่เท่ากัน ต่อไปเราจะเปรียบเทียบอักขระตัวที่สองและตัวสุดท้ายที่เท่ากันอีกครั้ง สุดท้ายเราเหลือเพียงตัวละครเดียวเท่านั้น ดังนั้นสตริงจึงเป็นพาลินโดรม
ค่าสตริง "reader":
-
อักขระจะเท่ากันจนถึงการเปรียบเทียบระหว่างองค์ประกอบสุดท้ายที่สองและที่สอง
เมื่อเปรียบเทียบอักขระตัวสุดท้ายที่สามและตัวที่สาม อักขระเหล่านี้จะไม่เท่ากัน ดังนั้นจึงไม่ใช่ palindrome
-
เราสามารถนำแนวคิดนี้ไปใช้โดยการเรียกซ้ำหรือใช้ตัวชี้สองตัว เราจะดำเนินการโดยใช้ตัวชี้สองตัว เราเริ่มต้นด้วยตัวชี้เริ่มต้นที่ 0 และตัวชี้สิ้นสุดที่ดัชนีสุดท้าย เราเริ่มเปรียบเทียบและหากอักขระเท่ากัน เราจะเพิ่มตัวชี้เริ่มต้นและลดตัวชี้สิ้นสุด (ซึ่งจะนำไปสู่อักขระตัวที่สองและตัวที่สอง และอื่นๆ)
-
เราจะคืนค่าเท็จเมื่อใด หากเราพบว่าอักขระสำหรับชุดพอยน์เตอร์ไม่เท่ากัน เราไม่จำเป็นต้องมองหาดัชนีเพิ่มเติมและเราสามารถคืนค่าเป็นเท็จได้
-
เมื่อไหร่จะคืนทรู? ในอีกกรณีหนึ่ง หาก string เป็น palindrome เราจะคืนค่า True เมื่อพอยน์เตอร์ทั้งคู่เท่ากัน (เหลือเพียง 1 อักขระที่จะตรวจสอบ) หรือตัวชี้เริ่มต้นเกินตัวชี้สิ้นสุด (ตรวจสอบอักขระทั้งหมดแล้ว) จึงคืนค่าเป็นจริง
ตัวอย่าง
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
