Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example
No.1
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
No.2
Input: “cbbd”
Output: “bb”
O(n^2) runtime, O(n) space – Dynamic programming
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public String (String s) {
String str = "";
int n = s.length();
if (n > 1000)
return str;
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i + 1 < 3 || dp[i+1][j-1]);
if (dp[i][j] && (j - i + 1) > str.length())
str = s.substring(i, j + 1);
}
}
return str;
}
|
O(n^2) runtime, O(1) space – Simpler solution
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 (String s) {
String str = "";
int n = s.length();
if (n > 1000)
return str;
for (int i = 0; i < n; i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int max = Math.max(len1, len2);
if (max > str.length())
str = s.substring(i - (max - 1) / 2, i + 1 + max / 2);
}
return str;
}
private int expandAroundCenter(String s, int i, int j) {
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
return j - i - 1;
}
|
近期评论