DP - 9: Longest Palindrome Subsequence
Source Code:https://thecodingsimplified.com/longe...
Solution - 1: Recursive Basic Solution
We start from start = 0 & end = length - 1
If values at start & end indexes are equal then recursively check for remaining start + 1 & end - 1 & add 2
It's not matching, then Get the maximum of lps(start, end - 1), lcs(start + 1, end)
Time Complexity: O(2^n)
Space Complexity: O(n)
Solution - 2: Top Down DP Solution
We start from start = 0 & end = length - 1 & initialize a 2D array
If values at start & end indexes are equal then recursively check for remaining start + 1 & end - 1 & add 2
It's not matching, then Get the maximum of lps(start, end - 1), lcs(start + 1, end)
At every position we check, if value is null means we need to find the value, if it's not null then value
exists in array & return from array.
Time Complexity: O(n * n)
Space Complexity: O(n * n)
Solution - 2: Bottom UP DP Solution
We initialize 2D array & represent string in 2D form
We start 1 loop starting from 2nd last row (i) & another loop from j = i + 1, which'll check every combination
If value matches, then 2 + arr[start + 1][end - 1]
If not matching, then Max(arr[start][end-1], arr[start+1][end])
at last we return arr[0][n-1]
Time Complexity: O(n * n)
Space Complexity: O(n * n)
Do Watch video for more info
CHECK OUT CODING SIMPLIFIED
/ codingsimplified
★☆★ VIEW THE BLOG POST: ★☆★
http://thecodingsimplified.com
I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.
★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★
/ codingsimplif. .
★☆★ Send us mail at: ★☆★
Email: [email protected]