Palindrome là gì?
Palindrome là một chuỗi giống nhau khi đọc từ trái sang phải hoặc từ phải sang trái. Nói cách khác, chuỗi palindrome là chuỗi có phần ngược lại của chuỗi ban đầu.
Ví dụ, civic, madam là palindromes.
Mèo không phải là một palindrome. Vì ngược lại của nó là tac, không bằng chuỗi ban đầu (cat).
Viết chương trình để tìm xem chuỗi đầu vào có phải là palindrome hay không.
Phương pháp 1 - Tìm Đảo ngược của chuỗi
-
Điều chính được yêu cầu trong chương trình là tìm mặt trái của chuỗi.
-
Đảo ngược có thể được tìm thấy bằng cách sử dụng bất kỳ phương pháp đảo ngược chuỗi nào. Chúng tôi sẽ sử dụng phương pháp cắt đơn giản để đảo ngược chuỗi. Cũng có thể sử dụng ‘’ .join (đảo ngược ()) có sẵn. Mặc dù có nhiều cách khác để đảo ngược một chuỗi, nhưng chúng tôi sẽ sử dụng một cách đơn giản.
-
So sánh chuỗi đã đảo ngược với chuỗi ban đầu.
-
Trả về true nếu cả hai chuỗi bằng nhau, nếu không trả về false.
Ví dụ
def isPalindrome(s):
rev=s[::-1]
if(rev==s):
return True
return False
print("Enter a string")
st=input()
print(isPalindrome(st)) Đầu ra
Enter a string madam True
Phương pháp 2 - Không tìm thấy mặt trái của chuỗi
Ý tưởng là liên tục so sánh các ký tự ở chỉ mục đầu tiên và chỉ mục cuối cùng của chuỗi cho đến khi chúng không bằng nhau.
Chúng ta sẽ thấy hai ví dụ mà không cần tìm ra mặt trái của một chuỗi -
Giá trị chuỗi "madam":
-
Chúng tôi so sánh các ký tự đầu tiên và cuối cùng bằng nhau, hơn nữa chúng tôi so sánh các ký tự thứ hai và thứ hai cuối cùng lại bằng nhau. Cuối cùng chúng ta chỉ còn lại một nhân vật. Do đó, chuỗi là một palindrome.
Giá trị chuỗi "trình đọc":
-
Các ký tự bằng nhau cho đến khi so sánh giữa phần tử thứ hai và phần tử cuối cùng thứ hai.
Khi các ký tự cuối cùng thứ ba và thứ ba được so sánh, chúng không bằng nhau, do đó nó không phải là palindrome.
-
Chúng ta có thể thực hiện ý tưởng này thông qua đệ quy hoặc sử dụng hai con trỏ. Chúng tôi sẽ triển khai bằng cách sử dụng hai con trỏ. Chúng tôi bắt đầu với con trỏ bắt đầu ở 0 và con trỏ kết thúc ở chỉ mục cuối cùng. Chúng tôi bắt đầu so sánh và nếu các ký tự bằng nhau, chúng tôi tăng dần con trỏ bắt đầu và giảm dần con trỏ kết thúc (do đó đưa chúng về ký tự thứ hai và ký tự cuối cùng thứ hai, v.v.).
-
Khi nào chúng ta trả về false? Nếu chúng tôi nhận thấy rằng các ký tự cho bất kỳ tập hợp con trỏ nào không bằng nhau, chúng tôi không cần tìm kiếm các chỉ mục khác và chúng tôi có thể trả về False.
-
Khi nào chúng ta trả về True? Trong trường hợp khác, nếu chuỗi là palindrome, chúng ta sẽ trả về True khi cả hai con trỏ trở nên bằng nhau (chỉ còn lại 1 ký tự để kiểm tra) hoặc con trỏ bắt đầu vượt quá con trỏ kết thúc (tất cả các ký tự đều được kiểm tra) và do đó trả về true.
Ví dụ
def isPalindrome(s):
rev=s[::-1]
if(rev==s):
return True
return False
print("Enter a string")
st=input()
print(isPalindrome(st)) Đầu ra
Enter a string reader False >>> Enter a string madam True