Trong nhiều năm, việc kiểm tra xem một chuỗi có phải là palindrome hay không đã trở thành một câu hỏi phỏng vấn mã hóa cổ điển. Điều này là do nó liên quan đến các khái niệm xung quanh thao tác và so sánh chuỗi và thậm chí các vòng lặp tùy thuộc vào việc triển khai. Và, câu hỏi không quá dài nên có thể hoàn thành trong thời gian hạn chế của một cuộc phỏng vấn. Bài viết này bao gồm triển khai để kiểm tra xem một chuỗi có phải là palindrome trong java và python hay không.
Hội chứng Pali là gì?
Theo Synny.com, định nghĩa của palindrome là "một từ hoặc cụm từ đọc ngược lại như tiến". Về cơ bản, nó có nghĩa là nếu bạn viết từ hoặc cụm từ ngược lại, nó sẽ giống hệt như khi viết về phía trước. Ví dụ, cha và mẹ là palindromes còn cha và mẹ thì không. Từ "palindrome" bắt nguồn từ hai từ gốc Hy Lạp, "palin" có nghĩa là một lần nữa và "dromos" có nghĩa là đường hoặc hướng. Nó được đặt ra bởi nhà viết kịch người Anh Ben Jonson vào thế kỷ 17.
Giải pháp
- Cách phổ biến và dễ dàng nhất để giải quyết câu hỏi là đảo ngược chuỗi trước rồi so sánh với chuỗi ban đầu. Cách tiếp cận này sẽ là O (n) trong ký hiệu big-O vì đảo ngược chuỗi là O (n).
- Một cách khác là bắt đầu so sánh các ký tự từ đầu đến cuối và tiếp tục cho đến khi bạn đến giữa. Cách tiếp cận này có độ phức tạp về thời gian là O (n / 2) nhưng trong ký hiệu big-O nó vẫn sẽ là O (n). Nhưng lợi thế của cách tiếp cận này là bạn có thể trả về False ngay khi bạn gặp sự không khớp đầu tiên, trong khi với cách tiếp cận đầu tiên, vì đảo ngược một chuỗi là bước đầu tiên nên độ phức tạp về thời gian sẽ luôn là O (n).
Triển khai Palindrome trong Python
Sau đây là mã để kiểm tra xem một chuỗi có phải là palindrome trong python hay không.
def is_palindrome (s): "" "Trả về True nếu đối số đã cho s là palindrome khác False" "" khẳng định (isinstance (s, str)), "Đối số s không thuộc loại "# Khẳng định nếu đối số đã cho thuộc loại return s [:: - 1] == s # So sánh phần ngược lại của chuỗi với chính nó nếu __name __ == "__ main__": print (is_palindrome ("dad")) def is_palindrome (word): "" "So sánh từng ký tự từ đầu đến cuối và trả về False khi xảy ra sự không khớp đầu tiên hoặc trả về True" "" i1, i2 = 0, len (word) -1 # Khởi tạo các con trỏ while i2> i1: if word [i1]! = word [i2]: # Nếu các ký tự không khớp thì không cần tiếp tục trả về False i1 + = 1 i2- = 1 return True if __name __ == "__ main__ ": print (is_palindrome (" cha ")) Triển khai Palindrome trong Java
Sau đây là mã để kiểm tra xem một chuỗi có phải là palindrome trong java hay không.
public class Palindrome {public static Boolean isPalindrome (String str) {StringBuilder sb = new StringBuilder (str); // StringBuilder có phương thức đảo ngược return sb.reverse (). ToString (). Equals (str); // So sánh phần ngược của chuỗi với chính nó} public static void main (String args []) {Boolean b = isPalindrome ("dad"); System.out.println (b); }}public class Palindrome {public static Boolean isPalindrome (String str) {int i1 = 0; int i2 = str.length () - 1; while (i2> i1) {if (str.charAt (i1)! = str.charAt (i2)) {return false; } i1 ++; i2--; } trả về true; } public static void main (String args []) {Boolean b = isPalindrome ("cha"); System.out.println (b); }} 
