online advertising

Wednesday, February 15, 2017

LeetCode OJ - Longest Palindromic Subsequence

Problem:

Please find the problem here.

Analysis:

Recently I have been reading up about some algorithms on bioinformatics and this one does look similar. The idea is you use interval dynamic programming.

Suppose we know the answer (i.e. the length of the longest palindromic subsequence) of all substrings with length less than d. We can use that information to compute the answer for all substring with length d.

To make the description simpler, let's abbreviate the longest palindromic subsequence to just LPS

There are a few possibilities, for the LPS, one of the following must hold:

  • The first character is paired with the last character.
  • The first character is paired with some other character but not the last one.
  • The first character is not included in the LPS.

For the first one, of course, the first and last one must be equal, and then we take the
LPS on the inner d - 2 characters. The length is therefore 2 + LPS(the inner d-2 characters)

For the second one, the last character cannot be paired with anything since the first one is paired with something else and apparently there is nothing before the first one. So this case the LPS is really just the LPS of the beginning d -1 characters.

For the third one, the first character cannot be paired with anything by design, so this case the LPS is really just the LPS of the last d -1 characters.

That make a very simple recurrence relation, define lps(i, j) be the length of the LPS of the substring of S from i to j inclusive.

lps(i, j) = max(lps(i, j - 1), lps(i + 1, j), 2 + lps(i + 1, j - 1))

Of course, the last term apply only if S[i] == S[j].

Solution:

We define lps2(i, len) = lps(i, i + len - 1). With this transformation, we know that we only need the last two lengths when computing the current length values, therefore we can save memory by keeping only the last two rows.

To avoid copying, I used a simple circular buffer scheme, that should make reading the code a little easier to understand this.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/longest-palindromic-subsequence/

#include "LEET_LONGEST_PALINDROMIC_SUBSEQUENCE.h"
#include <map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_LONGEST_PALINDROMIC_SUBSEQUENCE
{
    class Solution
    {
    public:
        int longestPalindromeSubseq(string s)
        {
            if (s.length() == 0)
            {
                return 0;
            }

            vector<int> result[3];
            result[0].resize(s.length());
            result[1].resize(s.length());
            result[2].resize(s.length());
            for (size_t i = 0; i < s.length(); i++)
            {
                // The maximum palindromic subsequence of a subsequence starting at i with length 0 is 0
                result[0][i] = 0;
                // The maximum palindromic subsequence of a subsequence starting at i with length 1 is 1
                result[1][i] = 1;
            }

            int current_row = 2;
            int last_row = 1;
            int last_last_row = 0;
            for (int length = 2; length <= s.length(); length++)
            {
                for (int i = 0; i + length <= s.length(); i++)
                {
                    int candidate = result[last_row][i];
                    candidate = max(candidate, result[last_row][i + 1]);
                    if (s[i] == s[i + length - 1])
                    {
                        candidate = max(candidate, 2 + result[last_last_row][i + 1]);
                    }
                    result[current_row][i] = candidate;
                }
                current_row = (current_row + 1) % 3;
                last_row = (last_row + 1) % 3;
                last_last_row = (last_last_row + 1) % 3;
            }
            return result[last_row][0];
        }
    };
};

using namespace _LEET_LONGEST_PALINDROMIC_SUBSEQUENCE;

int LEET_LONGEST_PALINDROMIC_SUBSEQUENCE()
{
    Solution solution;
    cout << solution.longestPalindromeSubseq("") << endl;
    cout << solution.longestPalindromeSubseq("bbbab") << endl;
    cout << solution.longestPalindromeSubseq("cbbd") << endl;
    return 0;
}

No comments :

Post a Comment