516. Longest Palindromic Subsequence

Medium

Description

給定一個字串 s，找出其中最長回文子序列的長度。

Example:

Input: s = “bbbab” Output: 4 (子序列 “bbbb”)

Intuition#

區間 DP：若兩端字元相同就收縮，否則取去掉左端或右端的較大值。

dp[i][j] 表示 s[i..j] 中最長回文子序列長度
若 s[i] == s[j]，則 dp[i][j] = dp[i+1][j-1] + 2
否則 dp[i][j] = max(dp[i+1][j], dp[i][j-1])
等價於求 s 和 s.reversed() 的 LCS

Approaches#

1: 區間 DP#

概念: 從短區間到長區間填表，dp[i][j] 為 s[i..j] 的最長回文子序列長度。
時間複雜度: O(n^2)
空間複雜度: O(n^2)

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        val n = s.length
        val dp = Array(n) { IntArray(n) }
        for (i in n - 1 downTo 0) {
            dp[i][i] = 1
            for (j in i + 1 until n) {
                dp[i][j] = if (s[i] == s[j]) {
                    dp[i + 1][j - 1] + 2
                } else {
                    maxOf(dp[i + 1][j], dp[i][j - 1])
                }
            }
        }
        return dp[0][n - 1]
    }
}

⭐2: 1D DP（空間優化）#

概念: 由於 dp[i][j] 只依賴 dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]，可以壓縮為一維陣列加一個暫存變數。
時間複雜度: O(n^2)
空間複雜度: O(n)

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        val n = s.length
        val dp = IntArray(n)
        for (i in n - 1 downTo 0) {
            dp[i] = 1
            var prev = 0 // dp[i+1][j-1]
            for (j in i + 1 until n) {
                val temp = dp[j]
                dp[j] = if (s[i] == s[j]) {
                    prev + 2
                } else {
                    maxOf(dp[j], dp[j - 1])
                }
                prev = temp
            }
        }
        return dp[n - 1]
    }
}

🔑 Takeaways#

Pattern: 區間 DP — dp[i][j] 依賴子區間，從短到長填表
關鍵技巧: 最長回文子序列等價於原字串與反轉字串的 LCS；區間 DP 可壓縮空間至 O(n)