LeetCode: Longest Palindromic Subsequence Posted on July 18, 2018July 26, 2020 by braindenny Longest Palindromic Subsequence Similar Problems: LeetCode: Valid Palindrome III CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #dynamicprogramming, #palindrome, #editdistance Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000. Example 1: Input: "bbbab" Output: 4 One possible longest palindromic subsequence is "bbbb". Example 2: Input: "cbbd" Output: 2 One possible longest palindromic subsequence is "bb". Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. // https://code.dennyzhang.com/longest-palindromic-subsequence // Basic Ideas: dynamic programming // optimal substructure: // Problem: the value of s[j...i] // if s[i] == s[j-1], f(s[j...i-1])+2 // if s[i] != s[j-1], max(f(s[j...i-1]), f(s[j+1...i])) // Terminiation condition: // For s[j...i], when i==j, return 1 // // Complexity: Time O(n^2), Space O(n^2) func longestPalindromeSubseq(s string) int { dp := make([][]int, len(s)) for i, _ := range dp { l := make([]int, len(s)) for j, _ := range l { l[j] = 1 } dp[i] = l } // dp[i][j]: s[j], s[j+1], s[j+2], ... s[i] for i:=1; i<len(s); i++ { for j:=i-1; j>=0; j-- { if s[i] == s[j] { // s[j], s[j+1...i-1], s[i] v := 2 if j+1 <= i-1 { v += dp[i-1][j+1] } dp[i][j] = v } else { // s[j+1...i] dp[i][j] = dp[i][j+1] if dp[i][j] < dp[i-1][j] { // s[j...i-1] dp[i][j] = dp[i-1][j] } } } } return dp[len(s)-1][0] } Post Views: 9