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"
Approach 1: Expand Around Center
So, What exactly is a Palindrome, which is a string that is the same boards as above, it is in Reverse so if we look at "bab", we will see that "bab" would be the same it was spelled forwards or backward. This place we can find that if we read any word like "abb" from left to right, is the same as read from right to left.
So. it has two criteria:
(1) the first Character = the Last Character;
(2) the inner word is also Palindromic;
So if you are ready to solve this problem I encourage you to try it on your own first but if you are ready to get started come with me to the follows coding.
So, to solve this problem we are going to use the idea of expending around the center of a palindrome, as you can see here, I have two different types of palindromes, one of these is an odd length, like "aba", and the other is an even length palindrome, likes "abba". So, to expand on the center, we need to define exactly what the center of a palindrome is. So we look here at the odd length palindrome "aba", the center of this palindrome is "b", and if we expand from the center out, we can check to see if the characters on either side that are mirroring each other are equal and if they are, we can increase the length of our palindrome in the odd lengths palindrome, the center of a palindrome is an individual character but in an even length palindrome we can see that the center is not a character but is the space between two characters. So the center and even length palindrome would like here between these two characters. And to expand around the center we would expand from between these two characters checking to see if 'b' and 'b' are equal, they are and expand again to check to see if 'a' and 'a' are equal they are and increase the length of our palindrome this way, so now that we know how to expand from the center and check for the size of a palindrome. Let's go through a quick example of using this strategy to solve this problem.
To solve this problem, we are going to initialize a result to zero and we are going to iterate through this string checking each character and space between the characters for the center of a palindrome, we are going to keep track of our longest palindrome and return the length of the longest palindrome at the end. In this problem, we are just going to be tracking the total length, but you could see that using this algorithm you can easily adapt it to returning the string which is what the prompt and the question is asking.
In fact, we could solve it in O(n^2) time using only constant space.
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n - 1 such center.
You might be asking why there are 2n - 1 but not n centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as "abba") and its center is between the two 'b's.
// Time complexity : O(n^2). Since expanding a palindrome around its center could take O(n) time, the overall complexity is O(n^2).
// Space complexity : O(1).
class Solution{
// Initialize a global variable;
String res = "";
public String longestPalindrome(String s) {
//corner case;
if(s == null || s.length() < 2) {
return s;
}
for(int i = 0; i < s.length(); i++) {
helper(s, i, i); // the center is odd length; assume odd length, try to extend Palindrome as possible
helper(s, i, i + 1); // the center is even length;
}
return res;
}
public void helper(String s, int left, int right) {
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
String cur = s.substring(left + 1, right);
if(cur.length() > res.length()) {
res = cur;
}
}
}
Approach 2: Dynamic Programming
it has two criteria:
(1) the first Character = the Last Character;
(2) the inner word is also Palindromic;
Firstly, we need to introduce the variable, it is a boolean two-dimensional variable, likes:
boolean[ ][ ] isPalindrome;
isPalindrome[i][j] means from index i character to index j character; if it is true, so it is a palindrome string, otherwise, it is not a palindrome string;
Thus, transfer to the machine language:
like " a b b a"
i j
(1). s.charAt(i) == s.charAt(j);
(2). isPalindrom[i + 1][j - 1] = true || j - i <= 2;
As we just indicate to use the dynamic programming technique, we will introduce a two-dimensional boolean array that is called isPalindrom;
// Time complexity : O(n^2) This gives us a runtime complexity of O(n^2).
// Space complexity : O(n^2) It uses O(n^2)space to store the table.
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
// corner case
if(s == null || len < 2) return s;
boolean[][] isPalindrome = new boolean[len][len];
int left = 0;
int right = 0;
for(int j = 1; j < len; j++) {
for(int i = 0; i < j; i++) {
//The code j - i <= 2 is checking whether the inner word between string.charAt(i) and string.charAt(j) only has at most one character. If only has just one character, the inner world is palindromic
//i is the index for left character and j is the index for the right character. isPalindrome[i + 1][j - 1] is a boolean indicating whether the inner word is palindromic or not. When isPalindrome[i + 1][j - 1] is true, it means the word of i +1 to j - 1 characters of the string is palindromic.
boolean isInnerWordPalindrom = isPalindrome[i + 1][j - 1] || (j - i <= 2);
if(s.charAt(i) == s.charAt(j) && isInnerWordPalindrom) {
isPalindrome[i][j] = true;
if(j - i > right - left) {
//we need to find the maximum palindrome
left = i;
right = j;
}
}
}
}
return s.substring(left, right + 1);
// in the java, the substring inclusive the left character but exclusive the right character, so we need plus one on the right index.
}
}
Approach 3: Manacher's Algorithm:
There is even an O(n) algorithm called Manacher's algorithm, explained. However, it is a non-trivial algorithm, and no one expects you to come up with this algorithm in a 45 minutes coding session. But, please go ahead and understand it, I promise it will be a lot of fun.
class Solution {
// process the t String;
public String longestPalindrome(String s) {
if(s == null || s.length() < 2) {
return s;
}
char[] t = new char[s.length() * 2 + 1]; //transformed string
int[] p = new int[t.length]; // p[i] is radius length of longest Palindromic string centered at i;
preprocess(s, t);
int center = 0, right = 0;
for(int i = 1; i < t.length - 1; i++) {
int mirror = 2 * center - i; //center - mirror = i - center, mirror is i's mirror based on center
// if i within pre-calculated palindrome
p[i] = right > i ? Math.min(p[mirror], right - i) : 1;
while(i + p[i] < t.length && i - p[i] >= 0 && t[i + p[i]] == t[i - p[i]]) p[i]++;
if(i + p[i] > right) {
center = i;
right = i + p[i];
}
}
center = 0;
int maxLen = 0;
for(int i = 1; i < p.length - 1; i++) {
if(p[i] > maxLen) {
center = i;
maxLen = p[i];
}
}
return s.substring((center - maxLen + 2) / 2, (center + maxLen) / 2);
}
private void preprocess(String s, char[] t) {
// Insert "#"
for(int i = 0; i < s.length(); i++) {
t[2 * i] = '#';
t[2 * i + 1] = s.charAt(i);
}
t[t.length - 1] = '#';
}
}
参考：
https://www.jianshu.com/p/238fa31f0999
https://segmentfault.com/a/1190000008484167?utm_source=tag-newest
https://www.cnblogs.com/grandyang/p/4475985.html
网友评论