โปรแกรม Java ตรวจสอบ String เป็น Palindrome

ปัญหาบางอย่างในการเขียนโปรแกรมมีสถานะเป็นแบบคลาสสิก โดยทั่วไปแล้ว งานดังกล่าวเกี่ยวข้องกับคณิตศาสตร์ และพวกเขาชอบถามนักเรียนที่เชี่ยวชาญด้านวิทยาการคอมพิวเตอร์มาก เช่นเดียวกับผู้หางานในการสัมภาษณ์ เป็นสิ่งที่ดีเพราะช่วยในการกำหนดความคิดของคุณในแบบโปรแกรมเมอร์ได้ค่อนข้างดีและฝึกมันด้วย ปัญหาอย่างหนึ่งคือการตรวจสอบว่าสตริงเป็นพาลินโดรมหรือไม่ และเราจะพิจารณาในบทความนี้

palindrome คืออะไรและทำไมสามารถค้นหาได้

พาลินโดรมคือชุดตัวเลข ตัวอักษร คำหรือข้อความที่อ่านเหมือนกันทั้งสองทิศทาง โดยสรุป พาลินโดรมสามารถเรียกชุดของอักขระใดก็ได้ที่มีความสมมาตรตรงกลาง คำนี้มาจากรากภาษากรีกที่มาจากคำว่า "วิ่งกลับ" (palin คือ "อีกครั้ง กลับ" และ dromos แปลว่า "วิ่ง") Palindrome ในภาษา Java มีความหมายเช่นเดียวกับความหมายทั่วไป ตัวอย่างของพาลินโดรม:

• พ.ศ. 2424
• อ๊าคคคคคคคคคคคคคคคคคคคคคคคคคคคคคคค
• โผล่
• กลางวัน
• ระดับ
• โรเตเตอร์
• โรงยิมของฉัน
• มาดามฉันคืออดัม
• บัดนี้ท่านได้รับชัยชนะในสงครามแล้ว!

1881 เป็นเลขพาลินโดรมและเลขอื่นคือสตริงพาลินโดรม ในบทความนี้ เราจะดูที่พาลินโดรมที่แสดงเป็นสตริง แต่อัลกอริทึมบางอย่างค่อนข้างจะใช้ได้กับพาลินโดรมชนิดอื่นใน Java ทำไมคุณถึงต้องการมองหา palindromes? อันที่จริง เราไม่จำเป็นต้องมองหาพาลินโดรมในชีวิตประจำวันบ่อยนัก มันเป็นงานที่เฉพาะเจาะจงมาก หากเราจำอัลกอริทึมสตริงได้ ในทางปฏิบัติแล้ว บ่อยครั้งโปรแกรมเมอร์สามารถค้นหาสตริงย่อยในสตริงได้ และไม่ต้องค้นหาพาลินโดรมหรือหมายเลข อย่างไรก็ตาม ปัญหาที่เกี่ยวข้องกับ palindromes มีการใช้งานที่สำคัญ อย่างแรกคือการเขียนโปรแกรมโอลิมปิก อาจมีภารกิจในการระบุพาลินโดรม แอปพลิเคชั่นที่สองที่เกี่ยวข้องกับโปรแกรมเมอร์มือใหม่คือการสัมภาษณ์ ในการสัมภาษณ์ทางเทคนิค คุณอาจถูกขอให้เขียนโปรแกรมอย่างรวดเร็วเพื่อตรวจสอบว่าสตริงนั้นเป็นพาลินโดรมหรือไม่ หรือแม้กระทั่งบนแผ่นกระดาษ ในทางวิทยาศาสตร์ การประยุกต์ใช้การค้นหาพาลินโดรมที่เป็นประโยชน์มากที่สุดคืออัลกอริทึมทางชีววิทยา จากข้อมูลของวิกิพีเดีย ความเป็นพาลินโดรมิซิตีของสารประกอบทางชีวภาพมีบทบาทสำคัญในคุณสมบัติของสารประกอบทางชีวภาพต่างๆ

ตัวอย่างรหัสอัลกอริทึม 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);


   }

}

ในวิธีการหลัก เราจะตรวจสอบสตริงพาลินโดรมิก “ระดับ” “เจ๋ง” “มาดาม” และ “เอาล่ะ ท่าน สงครามชนะแล้ว!” อย่างที่คุณเห็น อันแรก สาม และสี่คือพาลินโดรม แต่อันที่สองไม่ใช่ โปรแกรมจะให้อะไร? อันแรกคือพาลินโดรม อันที่สองไม่ใช่ อย่างไรก็ตาม เกิดอะไรขึ้นกับสามและสี่? ทำไมผลลัพธ์จึงเป็นเท็จ ? คุณอาจเดาได้แล้วว่าประเด็นคืออักขระบางตัวในสตริงนี้เป็นตัวพิมพ์ใหญ่และบางตัวเป็นตัวพิมพ์เล็ก และสำหรับ 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 ที่ยาวนานและมีความสุขของเรา “เอาล่ะ ท่าน สงครามชนะแล้ว!” ค่อนข้างง่าย ถ้าคุณจำได้ว่าช่องว่างและเครื่องหมายวรรคตอนทั้งหมดเหมือนกันกับตัวอักษรสำหรับ 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);


   }

}

อย่างน้อยผลลัพธ์คือสิ่งที่เราคาดหวังจากมัน: บางที หากคุณเพิ่งเริ่มเขียนโปรแกรม อาจเป็นเรื่องยากสำหรับคุณที่จะเข้าใจว่าอัลกอริทึมการข้ามสายอักขระและการเปรียบเทียบทำงานอย่างไร แน่นอนว่ามันจะดีกว่าที่จะจัดการกับสิ่งนี้ แต่คุณสามารถเขียนข้อความในเวอร์ชันที่เรียบง่ายผ่านอาร์เรย์ของอักขระซึ่งอันที่จริงแล้วคือสตริง คุณสามารถใช้เมธอด 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);


   }
}

ผลลัพธ์จะเหมือนกับในตัวอย่างแรก หากคุณต้องการ คุณสามารถปรับปรุงโปรแกรมนี้ได้เช่นเดียวกับที่เราทำกับตัวอย่างแรก เพื่อเสริมสิ่งที่คุณได้เรียนรู้ เราขอแนะนำให้คุณดูบทเรียนวิดีโอจากหลักสูตร Java ของเรา