ปัญหาบางอย่างในการเขียนโปรแกรมมีสถานะเป็นแบบคลาสสิก โดยทั่วไปแล้ว งานดังกล่าวเกี่ยวข้องกับคณิตศาสตร์ และพวกเขาชอบถามนักเรียนที่เชี่ยวชาญด้านวิทยาการคอมพิวเตอร์มาก เช่นเดียวกับผู้หางานในการสัมภาษณ์ เป็นสิ่งที่ดีเพราะช่วยในการกำหนดความคิดของคุณในแบบโปรแกรมเมอร์ได้ค่อนข้างดีและฝึกมันด้วย ปัญหาอย่างหนึ่งคือการตรวจสอบว่าสตริงเป็นพาลินโดรมหรือไม่ และเราจะพิจารณาในบทความนี้
palindrome คืออะไรและทำไมสามารถค้นหาได้
พาลินโดรมคือชุดตัวเลข ตัวอักษร คำหรือข้อความที่อ่านเหมือนกันทั้งสองทิศทาง โดยสรุป พาลินโดรมสามารถเรียกชุดของอักขระใดก็ได้ที่มีความสมมาตรตรงกลาง คำนี้มาจากรากภาษากรีกที่มาจากคำว่า "วิ่งกลับ" (palin คือ "อีกครั้ง กลับ" และ dromos แปลว่า "วิ่ง") Palindrome ในภาษา Java มีความหมายเช่นเดียวกับความหมายทั่วไป ตัวอย่างของพาลินโดรม:- พ.ศ. 2424
- อ๊าคคคคคคคคคคคคคคคคคคคคคคคคคคคคคคค
- โผล่
- กลางวัน
- ระดับ
- โรเตเตอร์
- โรงยิมของฉัน
- มาดามฉันคืออดัม
- บัดนี้ท่านได้รับชัยชนะในสงครามแล้ว!
ตัวอย่างรหัสอัลกอริทึม Palindrome
ลองคิดดู สตริงคือลำดับของอักขระ ซึ่งอาจกล่าวได้ว่าเป็นอาร์เรย์ของอักขระ มันจะสมเหตุสมผลที่สุดที่จะทำตามลำดับนี้จากทั้งสองด้านไปตรงกลางและเปรียบเทียบอักขระสุดโต่ง ถ้าจนกระทั่งเราไปถึงตรงกลางตัวละครทั้งหมดของเราจะตรงกัน เราก็มีพาลินโดรม มาสร้างเมธอดบูลีน validPalindrome(String s) เพื่อตรวจสอบว่า String เป็น palindrome หรือไม่ รหัส Java อยู่ที่นี่:
public class PalindromeTest1 {
//method to check if a string is palindrome
public static boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!"
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
ในวิธีการหลัก เราจะตรวจสอบสตริงพาลินโดรมิก “ระดับ” “เจ๋ง” “มาดาม” และ “เอาล่ะ ท่าน สงครามชนะแล้ว!” อย่างที่คุณเห็น อันแรก สาม และสี่คือพาลินโดรม แต่อันที่สองไม่ใช่ โปรแกรมจะให้อะไร?
เป็นระดับ palindrome? พาลินโดรมเจ๋งจริงหรือ? มาดามเป็นพาลินโดรมหรือไม่? False คือ ตอนนี้ครับ สงครามชนะแล้ว! พาลินโดรม? เท็จ
อันแรกคือพาลินโดรม อันที่สองไม่ใช่ อย่างไรก็ตาม เกิดอะไรขึ้นกับสามและสี่? ทำไมผลลัพธ์จึงเป็นเท็จ ? คุณอาจเดาได้แล้วว่าประเด็นคืออักขระบางตัวในสตริงนี้เป็นตัวพิมพ์ใหญ่และบางตัวเป็นตัวพิมพ์เล็ก และสำหรับ Java M และ m เป็นอักขระสองตัวที่แตกต่างกัน มาปรับปรุงโปรแกรมโดยคำนึงถึงความแตกต่างนี้ นี่คือโปรแกรมสำหรับตรวจสอบว่าสตริงเป็นพาลินโดรมที่แก้ปัญหาตัวพิมพ์ใหญ่และตัวพิมพ์เล็กหรือไม่
public class PalindromeTest2 {
//lowercase and uppercase characters should be treated the same:
public static boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!"
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
ครั้งนี้เราคาดการณ์ผลลัพธ์ได้มากขึ้น:
เป็นระดับ palindrome? พาลินโดรมเจ๋งจริงหรือ? มาดามเป็นพาลินโดรมหรือไม่? ความจริงก็คือ ตอนนี้ครับ สงครามได้รับชัยชนะแล้ว! พาลินโดรม? เท็จ
อืม…ไม่สามารถคาดเดาได้อย่างแน่นอน สถานการณ์ของ “มาดาม” เริ่มดีขึ้น แต่ palindrome ที่ยาวนานและมีความสุขของเรา “เอาล่ะ ท่าน สงครามชนะแล้ว!” ค่อนข้างง่าย ถ้าคุณจำได้ว่าช่องว่างและเครื่องหมายวรรคตอนทั้งหมดเหมือนกันกับตัวอักษรสำหรับ Java ดังนั้นเราจึงจำเป็นต้องปรับปรุงอัลกอริทึมของเราอีกครั้งเพื่อแก้ไขการกำกับดูแลนี้ มาสอนโปรแกรมของเราให้ละเว้นการเว้นวรรคและเครื่องหมายวรรคตอน พูดง่ายๆ คือ เราไม่สนใจอักขระที่ไม่ใช่ตัวเลขและตัวอักษรทั้งหมด นี่คือโปรแกรม palindrome ที่ได้รับการปรับปรุงใน Java
public class PalindromeTest3 {
//in addition to the above, ignore all non alphanumeric chars like punctuation and spaces
private static boolean isAlphanumeric(char c) {
return Character.isAlphabetic(c) || Character.isDigit(c);
}
public static boolean validPalindromeIgnorePunctuation(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
// skip chars we should ignore
while (j >= 0 && !isAlphanumeric(s.charAt(j))) j--;
while (i < s.length() && !isAlphanumeric(s.charAt(i))) i++;
// overskipped -> nothing left to validate
if (i >= j) return true;
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!";
boolean b1 = validPalindromeIgnorePunctuation(s1);
boolean b2 = validPalindromeIgnorePunctuation(s2);
boolean b3 = validPalindromeIgnorePunctuation(s3);
boolean b4 = validPalindromeIgnorePunctuation(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
อย่างน้อยผลลัพธ์คือสิ่งที่เราคาดหวังจากมัน:
เป็นระดับ palindrome? พาลินโดรมเจ๋งจริงหรือ? มาดามเป็นพาลินโดรมหรือไม่? ความจริงก็คือ ตอนนี้ครับ สงครามได้รับชัยชนะแล้ว! พาลินโดรม? จริง
บางที หากคุณเพิ่งเริ่มเขียนโปรแกรม อาจเป็นเรื่องยากสำหรับคุณที่จะเข้าใจว่าอัลกอริทึมการข้ามสายอักขระและการเปรียบเทียบทำงานอย่างไร แน่นอนว่ามันจะดีกว่าที่จะจัดการกับสิ่งนี้ แต่คุณสามารถเขียนข้อความในเวอร์ชันที่เรียบง่ายผ่านอาร์เรย์ของอักขระซึ่งอันที่จริงแล้วคือสตริง คุณสามารถใช้เมธอด StringBuffer.reverse เพื่อตรวจสอบว่าสตริงเป็นพาลินโดรมหรือไม่ มาทำเวอร์ชันที่ง่ายที่สุดโดยไม่ตรวจหาสัญลักษณ์ที่ไม่ใช่ตัวอักษรและตัวเลขและตัวพิมพ์ใหญ่และตัวพิมพ์เล็ก
public class PalindromeTest5 {
public static boolean validPalindrome(String s) {
StringBuffer buffer = new StringBuffer(s);
buffer.reverse();
String data = buffer.toString();
if (s.equals(data)) {
return true;
}
return false;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!";
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
ผลลัพธ์จะเหมือนกับในตัวอย่างแรก
เป็นระดับ palindrome? พาลินโดรมเจ๋งจริงหรือ? มาดามเป็นพาลินโดรมหรือไม่? False คือ ตอนนี้ครับ สงครามชนะแล้ว! พาลินโดรม? เท็จ
หากคุณต้องการ คุณสามารถปรับปรุงโปรแกรมนี้ได้เช่นเดียวกับที่เราทำกับตัวอย่างแรก เพื่อเสริมสิ่งที่คุณได้เรียนรู้ เราขอแนะนำให้คุณดูบทเรียนวิดีโอจากหลักสูตร Java ของเรา
GO TO FULL VERSION