5. Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
Example 1:
Example 2:
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters.
Solution:
很有意思的题目
class Solution {
public String longestPalindrome(String s) {
for (int len = s.length(); len > 0; len--){// check current len wether avaliable
for (int start = 0; start <= s.length() - len; start++){
// 0 , start <= start <= 5 - 4 = 1 start: [0, 1]
// 0, start <= start <= 5 - 3 = 2 start:[0, 1, 2]
// start <= s.length() - len make sure check the current len
if (check(start, start + len, s)){
//
// 0, 5, babad
return s.substring(start, start + len);
}
}
}
return "";
}
private boolean check(int i, int j, String s){
int left = i;
int right = j-1;
while(left < right){
if (s.charAt(left) != s.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}
// TC: O(n^3)
// SC: O(1)
/*
b a b a d
l r
0 end b a b
1 end a b a
2 end ba d
s len - 1 b a b a d
s
b a b a d
s end
b a b a d
s end
s:[ 0 , 1] length - end
b
for ( end ){
s
}
*/
Dynamic Programming:
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int[] ans = new int[]{0,0};
// ans stores the start and end indices of the longest palindromic substring found
// Initializes all single-character substrings as palindromes
// because any single character is inherently a palindrome.
for (int i = 0; i < n; i++){
dp[i][i] = true;
}
// 0 1 2 3 4
// b a b a d
//b T, _, _, _, _
//a _, T, _, _, _ i+1 (ba)
//b _, _, T, _, _
//a _, _, _, T, _
//d _, _, _, _, T
/// i
// dp[i][j] means from i to j whether palindromic
// This loop checks all consecutive character pairs in the string
// and marks them as palindromes in dp
// if they are the same. It also updates ans to these indices
// if a palindrome is found, considering two-character substrings.
for (int i = 0; i < n - 1; i++){
if (s.charAt(i) == s.charAt(i + 1)){
dp[i][i + 1] = true;
ans[0] = i;
ans[1] = i + 1;
};
}
// The outer loop gradually increases the difference between the start and
// end indices of the substrings being considered
// (diff represents the length of the substring minus one).
for (int diff = 2; diff < n; diff++){
// diff = 2; diff < 5; diff++
for (int i = 0; i < n - diff; i++){
// The inner loop iterates over all possible
// starting indices i for the current length.
// i = 0; i < 5-2 =3 ; i++ i: [0, 1, 2, 3]
int j = i + diff; // end point 0+2 = 2
// j is calculated as the end index of the substring.
if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]){
// It checks if the characters at the current start (i) and end (j) are the same
// if the substring between them (dp[i + 1][j - 1]) is a palindrome
// s.charAt(0) == s.charAt(2)
// dp[0+1][2-1] = dp[1][1]
dp[i][j] = true;
ans[0] = i;
ans[1] = j;
}
}
}
// diff = 2
// 0 1 2 3 4
// b a b a d
//b T, _, _, _, _
//a _, T, _, _, _ i+1 (ba)
//b _, _, T, _, _
//a _, _, _, T, _
//d _, _, _, _, T
/// i
int start = ans[0];
int end = ans[1];
return s.substring(start, end + 1);
// Returns the substring from start to end + 1
// (as the second argument of substring is exclusive).
}
}
// TC: O(n^2)
// SC: O(n^2)
Expand From Centers
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1){
return "";
}
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++){
int len1 = expandFromMiddle(s, i, i);
int len2 = expandFromMiddle(s, i, i+1);
int len = Math.max(len1, len2);
if (len > end - start){
start = i - ((len -1)/2);
end = i + (len /2);
}
}
return s.substring(start, end + 1);
}
public int expandFromMiddle(String s, int left, int right){
if (s == null || left > right ){
return 0;
}
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
return right - left - 1;
}
}
// TC: O(n^2)
// SC: O(1)
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
int start = 0;
int end = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j <= 1; j++){
int left = i;
int right = i + j;
while(left >= 0 && right <= n - 1 && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
left++;
right--;
if (right - left > end - start){
start = left;
end = right;
}
}
}
return s.substring(start, end + 1);
}
}
// TC: O(n^2)
// SC: O(1)
Manacher's Algorithm
啊这...
class Solution {
public String longestPalindrome(String s) {
StringBuilder sPrime = new StringBuilder("#");
for (char c: s.toCharArray()) {
sPrime.append(c).append("#");
}
int n = sPrime.length();
int[] palindromeRadii = new int[n];
int center = 0;
int radius = 0;
for (int i = 0; i < n; i++) {
int mirror = 2 * center - i;
if (i < radius) {
palindromeRadii[i] = Math.min(radius - i, palindromeRadii[mirror]);
}
while (i + 1 + palindromeRadii[i] < n &&
i - 1 - palindromeRadii[i] >= 0 &&
sPrime.charAt(i + 1 + palindromeRadii[i]) == sPrime.charAt(i - 1 - palindromeRadii[i])) {
palindromeRadii[i]++;
}
if (i + palindromeRadii[i] > radius) {
center = i;
radius = i + palindromeRadii[i];
}
}
int maxLength = 0;
int centerIndex = 0;
for (int i = 0; i < n; i++) {
if (palindromeRadii[i] > maxLength) {
maxLength = palindromeRadii[i];
centerIndex = i;
}
}
int startIndex = (centerIndex - maxLength) / 2;
String longestPalindrome = s.substring(startIndex, startIndex + maxLength);
return longestPalindrome;
}
}
// TC: O(n)
// SC: O(n)
Paper reference: https://dl.acm.org/doi/10.1145/321892.321896