[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