How to use Recursive method In Javascript
In this approach, we will use recursion to find the Longest Palindromic Subsequence (LPS) of a given string seq. It explores all possible substrings and returns the longest palindromic subsequence found.
Example: The below code explores all possible palindromic subsequences of the input string using the recursive approach.
Javascript
function max(x, y) { return x > y ? x : y; } function lps(seq, i, j) { if (i === j) { return { length: 1, subsequence: seq[i] }; } if (i + 1 === j && seq[i] === seq[j]) { return { length: 2, subsequence: seq[i] + seq[j] }; } if (seq[i] === seq[j]) { const innerResult = lps(seq, i + 1, j - 1); return { length: innerResult.length + 2, subsequence: seq[i] + innerResult.subsequence + seq[j], }; } const leftResult = lps(seq, i, j - 1); const rightResult = lps(seq, i + 1, j); return leftResult.length > rightResult.length ? leftResult : rightResult; } const seq = "w3wiki" ; const n = seq.length; const result = lps(seq.split( "" ), 0, n - 1); console.log ( "Longest Palindromic Subsequence: " , result.subsequence); console.log ( "Longest Palindromic Subsequence Length: " , result.subsequence.length); |
Longest Palindromic Subsequence: EEGEE Longest Palindromic Subsequence Length: 5
Longest Palindromic Subsequence in JavaScript
A Longest Palindromic Subsequence in JavaScript refers to the longest sequence of characters within a string that reads the same backward and forward. It’s a non-contiguous subsequence, and the goal is to find the maximum length of such subsequences in a given input string.
Example:
Input: str = “w3wiki”
Output: EEKEE, 5
Explanation: The longest palindromic subsequence we can get is of length 5.
There are more than 1 palindromic subsequences of length 5, for example: EEKEE, EESEE, EEFEE, …etc.