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)$


Comment