LeetCode之Longest Palindromic Subsequence(Kotlin)

169 阅读1分钟

问题:


方法: 算法的核心是动态规划,从短串推导到长串,当s[i] = s[j]时,dp[i][j] = dp[i+1][j-1] + 2;当 s[i] = s[j]时,dp[i][j] = maxOf(dp[i+1][j], dp[i][j-1]),类似斐波那契数列的演算过程,最后输出dp[0][s.lastIndex]即为最终结果。

具体实现:

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

fun main(args: Array<String>) {
    val input = "bbbab"
    val longestPalindromicSubsequence = LongestPalindromicSubsequence()
    println(longestPalindromicSubsequence.longestPalindromeSubseq(input))
}

有问题随时沟通

具体代码实现可以参考Github