Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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]
}
linkedin
github
slack

Post Views: 9
Posted in MediumTagged #dynamicprogramming, #palindrome, editdistance

Post navigation

LeetCode: N-ary Tree Postorder Traversal
LeetCode: N-ary Tree Level Order Traversal

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.