Reference: LeetCode
Difficulty: Medium

My Post: Java DP Solutions with Illustration T_T

Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

1
2
3
4
5
6
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

Analysis

Brute-Force

For each character i, we examine all substrings starting from index i and check if they are palindromic.

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
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int n = s.length();
String maxStr = "";
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
if (isValid(s, i, j) == true) {
if (j - i + 1 > maxStr.length()) { // update maxStr
maxStr = s.substring(i, j + 1);
}
}
}
}
return maxStr;
}

private boolean isValid(String s, int lo, int hi) {
int n = hi - lo + 1;
for (int i = 0; i < n / 2; ++i) {
if (s.charAt(lo + i) != s.charAt(hi - i)) {
return false;
}
}
return true;
}

Time: $O(N^3)$
Space: $O(1)$

Expansion From the Center

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
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int n = s.length();
StringBuilder longest = new StringBuilder();
for (int i = 0; i < n; ++i) {
findPalindrome(s, i, i, longest); // odd
findPalindrome(s, i, i + 1, longest); // even
}
return longest.toString();
}

private void findPalindrome(String s, int lo, int hi, StringBuilder longest) {
int n = s.length();
StringBuilder sb = new StringBuilder();
while (lo >= 0 && hi < n && s.charAt(lo) == s.charAt(hi)) {
if (lo == hi) {
sb.append(s.charAt(lo));
} else {
sb.insert(0, s.charAt(lo));
sb.append(s.charAt(hi));
}
--lo;
++hi;
}
if (sb.length() > longest.length()) {
longest.delete(0, longest.length());
longest.append(sb);
}
}

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

DP

Based on the brute-force solution, we can improve on it by avoiding unnecessary re-computation while validating palindromes. Consider the case ababa. If we already knew that bab is a palindrome, it is obvious that ababa must be a palindrome since the two end letters are the same.

So we can define dp[i][j] as true if the substring S(i, j) is a palindrome.

The recurrence is then obvious: dp[i][j] = (dp[i + 1][j - 1] && Si == Sj)

The base cases are: dp[i][i] = true, dp[i][i + 1] = (Si == Si+1).

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 + 2.

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
38
39
40
41
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int n = s.length();
boolean[][] dp = generateDP(s);
// Check each substring
int maxLen = 0;
int[] maxIdx = new int[] { 0, 0 };
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
if (dp[i][j] == true) {
if (j - i + 1 > maxLen) {
maxLen = j - i + 1;
maxIdx[0] = i;
maxIdx[1] = j;
}
}
}
}
return s.substring(maxIdx[0], maxIdx[1] + 1);
}

private boolean[][] generateDP(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
// Init
for (int i = 0; i < n; ++i) { // diagonal
dp[i][i] = true;
}
for (int i = 0; i < n - 1; ++i) { // one line below diagonal
dp[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
}
// DP
for (int i = n - 3; i >= 0; --i) {
for (int j = i + 2; j < n; ++j) {
dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
}
}
return dp;
}

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


Comment