การใช้งาน Longest palindrome in string ในภาษา Java แบบง่ายๆ พร้อมตัวอย่าง

บทความ: การค้นหา Longest Palindrome ในสายอักขระ (String) ด้วย Java

ความรู้ด้านการเขียนโปรแกรมเป็นทักษะที่มีความต้องการสูงในตลาดแรงงานยุคดิจิทัล ซึ่งการเรียนรู้ภาษาโปรแกรมมิ่งเป็นเรื่องจำเป็นไม่น้อย หากคุณกำลังมองหาสถานที่ที่จะช่วยพัฒนาทักษะการเขียนโปรแกรม ไม่ว่าจะเป็น Java, Python, JavaScript หรือภาษาอื่นๆ ทาง EPT พร้อมที่จะนำพาคุณไปสู่โลกแห่งการเขียนโค้ดอย่างมืออาชีพ

ในบทความนี้ ฉันจะมานำเสนอหัวข้อที่น่าสนใจ ซึ่งก็คือการค้นหา "Longest Palindromic Substring" หรือประโยคซ้ำย้อนกลับที่ยาวที่สุดในสายอักขระ (String) โดยใช้ภาษา Java การค้นหาแบบนี้มีความน่าสนใจในทางทฤษฎีและยังสามารถนำไปประยุกต์ใช้ในโลกจริงได้หลากหลายวิธี ไม่ว่าจะเป็นในการพัฒนาโปรแกรมที่ต้องการแยกวิเคราะห์ข้อความ, การวิเคราะห์ DNA sequence ในชีววิทยา, หรือแม้แต่การเพิ่มความสามารถในการค้นหาของเครื่องมือการทำ index ข้อความเชิงปริมาณ

ก่อนอื่น เรามาทำความเข้าใจกับคำว่า "Palindrome" คืออะไร ในทางคณิตศาสตร์หรือด้านการเขียนโปรแกรม Palindrome คือข้อความที่อ่านจากหน้าไปหลังหรือจากหลังไปหน้าแล้วได้ผลลัพธ์เหมือนกัน เช่น "radar", "level", หรือ "กางเขน" เป็นต้น ในการค้นหา longest palindromic substring, เราต้องการหา substring ที่ยาวที่สุดภายใน string ที่กำหนด เช่นใน "babad" ลำดับยาวที่สุดที่เป็น palindrome คือ "bab" หรือ "aba" ทั้งสองนี้มีความยาวเท่ากันและเป็น palindrome

เรามาดูตัวอย่างโค้ดในการค้นหา longest palindromic substring ใน Java กันครับ:

ตัวอย่างที่ 1: วิธี Brute Force

 public class PalindromeExample {
    // ฟังก์ชันสำหรับตรวจสอบว่าข้อความเป็น palindrome
    public static boolean isPalindrome(String s) {
        for(int i = 0; i < s.length()/2; i++) {
            if(s.charAt(i) != s.charAt(s.length()-1-i)) {
                return false; // ไม่เป็น palindrome
            }
        }
        return true; // เป็น palindrome
    }

    // ฟังก์ชันสำหรับค้นหา longest palindrome substring
    public static String longestPalindrome(String s) {
        String longest = "";
        for(int i = 0; i < s.length(); i++) {
            for(int j = i; j <= s.length(); j++) {
                String sub = s.substring(i, j);
                if(isPalindrome(sub) && sub.length() > longest.length()) {
                    longest = sub;
                }
            }
        }
        return longest; // คืนค่า palindrome ที่ยาวที่สุด
    }

    public static void main(String[] args) {
        String str = "babad";
        System.out.println("Longest palindrome substring is: " + longestPalindrome(str));
    }
}

วิธี brute force นี้สนมใจเรียบง่ายแต่มีประสิทธิภาพต่ำ เนื่องจากมีเวลาทำงานเป็น O(n^3) สำหรับ string ที่มีความยาว n หมายความว่าจะใช้เวลามากหาก string มีขนาดใหญ่ขึ้น

ตัวอย่างที่ 2: การแก้ปัญหาแบบ Dynamic Programming

เราสามารถใช้ Dynamic Programming เพื่อลดเวลาทำงานโดยการจดจำการคำนวณที่เคยทำไปแล้วสำหรับ substring นั้นๆ ดังตัวอย่างโค้ดด้านล่าง:

 public class PalindromeExample {

    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }

        int start = 0, end = 0;
        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int j = 0; j < s.length(); j++) {
            for (int i = 0; i <= j; i++) {
                boolean isInnerWordPalindrome = (dp[i + 1][j - 1] || j - i <= 2);

                if (s.charAt(i) == s.charAt(j) && isInnerWordPalindrome) {
                    dp[i][j] = true;

                    if ((j - i) > (end - start)) {
                        start = i;
                        end = j;
                    }
                }
            }
        }

        return s.substring(start, end + 1);
    }

    public static void main(String[] args) {
        String str = "babad";
        System.out.println("Longest palindrome substring is: " + longestPalindrome(str));
    }
}

ตัวอย่างที่ 3: การใช้ Manacher's Algorithm

Manacher's Algorithm เป็นอัลกอริทึมที่ออกแบบมาเพื่อค้นหา longest palindromic substring โดยเฉพาะ มีประสิทธิภาพสูงมาก และเวลาทำงานเป็น O(n)

 // ตัวอย่างนี้ค่อนข้างซับซ้อนและต้องการความเข้าใจที่ดีในทฤษฎี ฉันขออนุญาตไม่นำเสนอโค้ดนี้ในที่นี้ เพื่อความสั้นและชัดเจนของบทความ

อย่างไรก็ตาม Manacher's Algorithm อาจไม่เหมาะสำหรับผู้เรียนที่เพิ่งเริ่มต้นเขียนโปรแกรม เนื่องจากมีความซับซ้อนในทางทฤษฎีและการดำเนินงาน

Usecase ในชีวิตจริง:

- การพัฒนาเครื่องมือค้นหา: การตรวจหาความเป็น palindrome ใน keyword สามารถช่วยให้ปรับปรุงความสามารถในการค้นหาของเครื่องมือได้

- การวิเคราะห์ดีเอ็นเอ: Longest palindrome สามารถบ่งชี้ถึงลำดับที่มีความสำคัญในดีเอ็นเอและใช้ในการวิจัยทางชีววิทยา

- การโปรแกรมที่เกี่ยวข้องกับข้อความ: สามารถใช้ในการพัฒนาเกมปริศนา, เครื่องมือตรวจสอบความถูกต้องของข้อความ ฯลฯ

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

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