[LeetCode] 516. Longest Palindromic Subsequence

 轉自LeetCode

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

 

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

 

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

Solution

也可以用DP的概念來解

dp[i][j] 代表 s[i] 到 s[j]  可以形成的回文串長度

公式如下

if s[i] = s[j]，dp[i][j] = dp[i+1][j-1] + 2。長度可以+2是因為前面多了s[i]，後面多了s[j]

if s[i] != s[j]，dp[i][j] = max(dp[i+1][j], dp[i][j-1])。從捨棄 i+1和j-1中，挑一個最大值

code 如下

kotlin

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

view raw longest_palindromic_subsequence.kt hosted with ❤ by GitHub