โปรแกรม Java หา Longest Palindromic Subsequence (LPS)

แนวคิด: Dynamic Programming + LCS

Longest Palindromic Subsequence = Longest Common Subsequence (LCS) ระหว่างสตริงต้นฉบับกับสตริงที่กลับลำดับ (reverse)

ตัวอย่างโค้ด (เวอร์ชันปรับปรุง)

public class Demo {
    // LCS แบบปกติ คืนค่าสตริง LPS
    static String longestSeq(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];
        
        // สร้างตาราง DP
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // Reconstruct LPS string
        StringBuilder lps = new StringBuilder();
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                lps.append(s1.charAt(i - 1));
                i--; j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        return lps.reverse().toString();
    }
    
    static String longestPalSubseq(String str) {
        String rev = new StringBuilder(str).reverse().toString();
        return longestSeq(str, rev);
    }
    
    public static void main(String[] args) {
        String str = "HelloHelloo";
        System.out.println("Longest palindromic subsequence: " + longestPalSubseq(str));
    }
}

ผลลัพธ์

Longest palindromic subsequence: llell

คำอธิบาย: ใช้ตาราง DP ขนาด (n+1)×(m+1) เก็บความยาว LCS แล้ว trace back สร้างสตริง LPS Complexity: O(n²) time, O(n²) space

การเพิ่มประสิทธิภาพ Space

ลด space เป็น O(n) ได้โดยเก็บแค่ 2 แถว (current, previous) แต่จะ reconstruct string ไม่ได้ ต้องเก็บตารางเต็มหรือใช้วิธีอื่น