Reference: LeetCode
Difficulty: Medium

My Post: [Java] DP Solutions with Graphs!

Problem

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
2
3
4
5
6
7
Input: "bbbab"
Output: 4
Exp: "bbbb"

Input: "cbbd"
Output: 2
Exp: "bb"

Analysis

Brute-Force

Find the recurrence.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int longestPalindromeSubseq(String s) {
  if (s == null || s.length() == 0) {
    return 0;
  }
  int n = s.length();
  return palSubseq(s, 0, n - 1);
}

private int palSubseq(String s, int lo, int hi) {
  if (lo == hi) {
    return 1;
  }
  if (lo > hi) {
    return 0;
  }
  if (s.charAt(lo) == s.charAt(hi)) {
    return palSubseq(s, lo + 1, hi - 1) + 2;
  } else {
    return Math.max(palSubseq(s, lo + 1, hi), palSubseq(s, lo, hi - 1));
  }
}

Time: $O(2^N)$ in the worst case when $T(N) = 2T(N - 1)$. In the best case, it is $O(N)$.
Space: $O(N)$

DP (memoization)

Based on the brute-force solution, we found repeated calculation. We can use memoization to optimize the time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int longestPalindromeSubseq(String s) {
  if (s == null || s.length() == 0) {
    return 0;
  }
  int n = s.length();
  int[][] mem = new int[n][n];
  // init
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      mem[i][j] = -1;
    }
  }
  return palSubseq(s, 0, s.length() - 1, mem);
}

private int palSubseq(String s, int lo, int hi, int[][] mem) {
  if (lo == hi) {
    return 1;
  }
  if (lo > hi) {
    return 0;
  }
  if (s.charAt(lo) == s.charAt(hi)) {
    if (mem[lo + 1][hi - 1] == -1) {
      mem[lo + 1][hi - 1] = palSubseq(s, lo + 1, hi - 1, mem);
    }
    return mem[lo + 1][hi - 1] + 2;
  } else {
    if (mem[lo + 1][hi] == -1) {
      mem[lo + 1][hi] = palSubseq(s, lo + 1, hi, mem);
    }
    if (mem[lo][hi - 1] == -1) {
      mem[lo][hi - 1] = palSubseq(s, lo, hi - 1, mem);
    }
    return Math.max(mem[lo + 1][hi], mem[lo][hi - 1]);
  }
}

Time: $O(N^2)$
Space: $O(N^2)$

DP (2D)

Define: We denote dp[i][j] as the longest palindromic subsequence’s length in the substring s(i, j).

Recurrence:

  • If s[i] == s[j], then dp[i][j] = dp[i + 1][j - 1] + 2.
  • Else, then dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).

Initialization: Check out the base cases in the brute-force solution.

Note: Determining ranges of i and j would be easy if you pick a starting point in the graph to get some intuition. For example, in this case j starts from i + 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int longestPalindromeSubseq(String s) {
  if (s == null || s.length() == 0) {
    return 0;
  }
  int n = s.length();
  int[][] dp = new int[n][n];
  // Init
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i > j)  dp[i][j] = 0;
      if (i == j) dp[i][j] = 1;
    }
  }
  // DP
  for (int i = n - 2; i >= 0; --i) {
    for (int j = i + 1; j < n; ++j) {
      if (s.charAt(i) == s.charAt(j)) {
        dp[i][j] = dp[i + 1][j - 1] + 2;
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[0][n - 1];
}

Time: $O(N^2)$
Space: $O(N^2)$