Given a string s, find the longest substring in s. You can assume that s is at most 1000.
Example:
Input:"babad"Output:"bab"Note:"aba"That's a valid answerCopy the code
Example:
Input:"cbbd"Output:"bb"
Copy the code
Train of thought
The original idea is to do it the dumbest way possible, which is to find all the strings and then palindrome all the substrings and record the length. You can imagine the time complexity of this, O(n) times O(n) times O(n)=O(n^3). So this kind of affirmation can’t meet our requirements.
Ok, so let’s analyze this problem, and let’s specialize this problem;
-
Suppose the input string length is 1
So the longest palindrome of this string is itself, length 1
-
If the string is of length 2, it requires that the two characters be equal if it is a palindrome string.
That is: s[I] == s[j] and i-j=1(here I is assumed to be the larger index position)
-
What if I minus j is greater than 1? Is it ok to meet the following conditions as long as:
That is: S [I] == S [j] &&S [i-1] == S [j+1]
The idea is dynamic programming. The theoretical text on dynamic programming is not code, interested partners wide to learn by themselves. Here is the code for this problem:
public String longestPalindrome(String s) {
// A string of length 1 returns the current string
if (s.length()==1) {return s;
}
// If the length is 2 and the two characters are equal, return
if (s.length()==2&&s.charAt(0)==s.charAt(1)) {return s;
}
// isLongestPalindrome[j][I]
// isLongestPalindrome[1][5] = = true indicates that the substring from 1 to 5 is a palindrome.
boolean[][] isLongestPalindrome = new boolean[s.length()][s.length()];
// The longest palindrome string starts with a maximum of 0
int maxlen = 0;
// Start index position for maxlen
int beginIndex = 0;
// The end index position for maxlen
int lastIndex = 0;
for (int i=0; i<s.length(); i++){int j=i;
while(j>=0) {// The third condition above is satisfied, i.e. the current s.charat (I)== s.charat (j) and
// and s[j+1 to i-1] is also a palindrome string
if (s.charAt(i)==s.charAt(j)&&(i-j<2||isLongestPalindrome[j+1][i-1])){
isLongestPalindrome[j][i]=true;
if (maxlen < i-j+1) {
beginIndex = j;
lastIndex = i+1;
maxlen = i-j+1; } } j--; }}return s.substring(beginIndex,lastIndex);
}
Copy the code