Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode 516 - longest palindromic subsequence - pass online judge
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Leetcode516_longestPalindromicSubsequence
{
/// <summary>
/// Leetcode 516: longest palindromic subsequence
/// https://leetcode.com/problems/longest-palindromic-subsequence/#/description
/// </summary>
class Program
{
static void Main(string[] args)
{
var test = "abbccdbda";
int length = longestPalindromeSubseq(test);
}
public static int longestPalindromeSubseq(String s) {
if( s == null || s.Length == 0)
{
return 0;
}
int length = s.Length;
var subsequence = new int[length][];
for (int i = 0; i < length; i++)
{
subsequence[i] = new int[length];
}
// assuming i < j, subsequence from index i to index j
for (int i = length - 1; i >= 0; i--)
{
subsequence[i][i] = 1;
for (int j = i + 1; j < length; j++)
{
if (s[i] == s[j])
{
subsequence[i][j] = subsequence[i + 1][j - 1] + 2;
}
else
{
subsequence[i][j] = Math.Max(subsequence[i + 1][j], subsequence[i][j - 1]);
}
}
}
return subsequence[0][length - 1];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.