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:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
Solution
- brute force
- 注意substring 左闭右开 [)
// brute force
class Solution {
public String longestPalindrome(String s) {
int max = 0;
String maxStr = "";
for (int i = 0; i < s.length(); ++i) {
String res = longest(s, i, i);
if (res.length() > max) {
max = res.length();
maxStr = res;
}
}
for (int i = 0; i < s.length(); ++i) {
String res = longest(s, i, i+1);
if (res.length() > max) {
max = res.length();
maxStr = res;
}
}
return maxStr;
}
private String longest(String s, int i, int j) {
// System.out.println(s + " " + i + j);
if (i < 0 || j >= s.length()) {
return "";
}
while (i >= 0 && j < s.length() &&
s.charAt(i) == s.charAt(j)) {
i -= 1;
j += 1;
}
i++;
return i > j ? "" : s.substring(i, j);
}
}
// Manacher's Algorithm
